无向图的链接表指针表示法c++

无向图的邻接表指针表示法是一种常用的图的表示方法，它使用链表来表示图中每个顶点的邻接点。在C++中，可以通过定义两个结构体来实现邻接表的表示。

首先，定义一个结构体来表示图中每个顶点的邻接点，命名为EdgeNode。该结构体包含两个成员变量：一个整型变量用于存储邻接点的序号，一个指针变量用于指向下一个邻接点。

struct EdgeNode {
    int adjvex; // 邻接点的序号
    EdgeNode* next; // 指向下一个邻接点的指针
};

接下来，定义一个结构体来表示图中每个顶点，命名为VNode。该结构体包含两个成员变量：一个用于存储顶点的数据，一个指针变量用于指向第一个邻接点。

struct VNode {
    int data; // 顶点的数据
    EdgeNode* firstEdge; // 指向第一个邻接点的指针
};

通过以上两个结构体的定义，可以构建一个邻接表来表示无向图。邻接表是一个由VNode结构体组成的数组，数组的每个元素表示图中的一个顶点，通过firstEdge指针可以找到该顶点的邻接点链表。

下面是一个示例代码，演示了如何使用邻接表指针表示法来表示无向图：

#include <iostream>
using namespace std;

const int MAX_VERTICES = 100; // 最大顶点数

struct EdgeNode {
    int adjvex;
    EdgeNode* next;
};

struct VNode {
    int data;
    EdgeNode* firstEdge;
};

class Graph {
private:
    VNode adjList[MAX_VERTICES];
    int numVertices;
public:
    Graph(int n) {
        numVertices = n;
        for (int i = 0; i < numVertices; i++) {
            adjList[i].data = i; // 顶点的数据为顶点的序号
            adjList[i].firstEdge = nullptr; // 初始化邻接点链表为空
        }
    }

    void addEdge(int start, int end) {
        EdgeNode* newNode = new EdgeNode;
        newNode->adjvex = end;
        newNode->next = adjList[start].firstEdge;
        adjList[start].firstEdge = newNode;

        newNode = new EdgeNode;
        newNode->adjvex = start;
        newNode->next = adjList[end].firstEdge;
        adjList[end].firstEdge = newNode;
    }

    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            cout << "顶点 " << adjList[i].data << " 的邻接点：";
            EdgeNode* p = adjList[i].firstEdge;
            while (p != nullptr) {
                cout << p->adjvex << " ";
                p = p->next;
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph(4); // 创建一个有4个顶点的图

    graph.addEdge(0, 1); // 添加边
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 3);

    graph.printGraph(); // 打印图的邻接表表示

    return 0;
}

运行以上代码，输出结果为：

顶点 0 的邻接点：2 1 
顶点 1 的邻接点：3 0 
顶点 2 的邻接点：3 0 
顶点 3 的邻接点：2 1