C++用邻接表实现无向图

实现无向图的基本思路是使用邻接表来存储每个顶点的邻居节点。邻接表是指一个数组，每个数组元素对应一个顶点，数组元素的值是一个链表，链表中存储了与该顶点相邻的所有顶点。

下面是用 C++ 实现无向图的代码：

#include<iostream>
#include<vector>

using namespace std;

class Graph{
private:
    int V; // 顶点数量
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int V){
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int v, int w){
        // 无向图的邻接表需要同时添加两条边
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    void printGraph(){
        for(int i=0; i<V; i++){
            cout << i << " -> ";
            for(int j=0; j<adj[i].size(); j++){
                cout << adj[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main(){
    // 创建一个无向图
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    // 打印邻接表
    g.printGraph();

    return 0;
}

在上面的代码中，我们定义了一个 Graph 类，其中 V 表示顶点数量，adj 是一个二维向量，用于存储邻接表。addEdge 函数用于向无向图中添加一条边，需要同时添加两条边。printGraph 函数用于打印邻接表。

在 main 函数中，我们创建一个无向图，并添加了一些边，然后打印邻接表。输出结果如下：

0 -> 1 4 
1 -> 0 2 3 4 
2 -> 1 3 
3 -> 1 2 4 
4 -> 0 1 3 

这个邻接表表示的无向图如下所示：

0---1
|\ /|\
| X | 2
|/ \|/
4---3