pta采用邻接表创建无向图

### 使用邻接表创建无向图

#### 方法概述
为了使用邻接表创建无向图，需要定义两个主要结构体来表示顶点和边的关系。具体来说：

- **VNode (头结点)**：用于保存每个顶点的信息以及指向第一条关联边的指针。
- **ENode (表结点)**：用来记录每条边的目标顶点编号及其权重，并链接到下一条从同一源顶点出发的边。

这些结构被封装在一个更大的 `ALGraph` 结构体内，该结构不仅包含了上述两种类型的数组还维护着整个图形的一些基本信息，比如顶点数目 (`vexnum`) 和 边数(`edgenum`) 等属性[^2]。

下面是一个完整的 C++ 示例程序展示如何通过邻接表构建并打印一个简单的无向图:

#include <iostream>
using namespace std;

#define MAXVEX 20 // 定义最大可能存在的定点数量

// 枚举不同类型图表种类
typedef enum { UDG } GraphKind;

// 表结点(Edge Node)，即链表中的节点
struct ENode {
    int adjvex;        // 邻接点的位置索引
    struct ENode* nextarc; // 下一条弧对应的表结点地址
};

// 头结点(Vertex Node), 即邻接表中每一个元素
struct VNode {
    char vex;          // 存储当前顶点的名字或其他标识符
    ENode* firstarc;   // 指向第一个邻接点位置的指针
};

// 整个图的数据结构描述
struct ALGraph {
    VNode vertices[MAXVEX];
    int vexnum;
    int edgenum;
    GraphKind kind;
};

void CreateUDG(ALGraph& G);
void PrintUDG(const ALGraph& G);

int main() {
    ALGraph graph;
    
    cout << "Creating an undirected graph..." << endl;
    CreateUDG(graph);  
    cout << "\nThe created undirected graph is as follows:" << endl;
    PrintUDG(graph);

    return 0;
}

/// @brief 函数功能: 创建一个无向图
/// @param[out] G 将要初始化好的无向图对象引用
void CreateUDG(ALGraph &G){
    cin >> G.vexnum >> G.edgenum;
    for(int i=0;i<G.vexnum;++i){ 
        cin>>G.vertices[i].vex;
        G.vertices[i].firstarc=nullptr;
    }
    for(int k=0;k<G.edgenum;++k){
        int v1,v2;
        cin>>v1>>v2;
        
        // 插入新边至第v1个顶点处
        ENode *e=(ENode*)malloc(sizeof(struct ENode));
        e->adjvex=v2;
        e->nextarc=G.vertices[v1].firstarc;
        G.vertices[v1].firstarc=e;

        // 因为是无向图所以也要插入反方向的新边至第v2个顶点处
        e=(ENode*)malloc(sizeof(struct ENode));
        e->adjvex=v1;
        e->nextarc=G.vertices[v2].firstarc;
        G.vertices[v2].firstarc=e;
    }
}

/// @brief 打印给定的无向图
/// @param[in] G 被打印出来的无向图实例
void PrintUDG(const ALGraph &G){
    for(int i=0;i<G.vexnum;++i){
        printf("%c:",G.vertices[i].vex);
        for(auto p=G.vertices[i].firstarc;p!=nullptr;p=p->nextarc)
            printf(" -> %d",p->adjvex);
        puts("");
    }
}

此代码片段展示了怎样利用用户输入动态建立一张具有指定顶点集与边集关系的无向图，并最终将其可视化输出以便验证结果正确性。