C++中邻接表实现无向图的方法

资源摘要信息:"C++实现无向图的邻接表表示方法" 无向图是图论中非常基础且重要的概念，在计算机科学中有着广泛的应用，如网络图、社交网络分析等。在C++中，使用邻接表表示无向图是一种常见的数据结构实现方式，它能够有效地存储图的信息并支持各种图操作。本知识点将详细介绍如何用C++实现无向图的邻接表表示，并解释其背后的基本原理和操作方法。 ### 邻接表数据结构 邻接表是一种用于表示图的数据结构，特别适合于稀疏图。它包含两部分： 1. **顶点表**：存储图中所有顶点。 2. **边表**：每个顶点对应一个链表，链表中存储与该顶点相邻接的所有顶点。 ### C++实现 在C++中，我们可以使用结构体和链表来实现邻接表。下面是基本的实现步骤： #### 定义顶点和边表节点结构体 ```cpp #include <iostream> #include <vector> // 边表节点 struct EdgeNode { int adjvex; // 邻接点域，存储该顶点对应的下标 EdgeNode* next; // 链域，指向下一条弧的指针 EdgeNode(int x, EdgeNode* n = nullptr) : adjvex(x), next(n) {} }; // 顶点表节点 struct VertexNode { int data; // 顶点信息 EdgeNode* firstedge; // 边表头指针 VertexNode(int x) : data(x), firstedge(nullptr) {} }; ``` #### 定义图结构体 ```cpp // 图结构体 struct Graph { int numVertices; // 顶点个数 std::vector<VertexNode> vertices; // 顶点数组 Graph(int n) : numVertices(n) { vertices.resize(n); } }; ``` #### 添加边 ```cpp // 添加边，将v1和v2连接 void addEdge(Graph& graph, int v1, int v2) { // v1边表插入v2 EdgeNode* newEdge = new EdgeNode(v2); newEdge->next = graph.vertices[v1].firstedge; graph.vertices[v1].firstedge = newEdge; // v2边表插入v1（无向图需双向连接） newEdge = new EdgeNode(v1); newEdge->next = graph.vertices[v2].firstedge; graph.vertices[v2].firstedge = newEdge; } ``` #### 遍历图 遍历无向图的邻接表通常有两种方法：深度优先搜索(DFS)和广度优先搜索(BFS)。 ```cpp // 深度优先遍历 void DFS(Graph& graph, int v, bool visited[]) { visited[v] = true; std::cout << graph.vertices[v].data << " "; EdgeNode* node = graph.vertices[v].firstedge; while (node) { int w = node->adjvex; if (!visited[w]) { DFS(graph, w, visited); } node = node->next; } } // 广度优先遍历 void BFS(Graph& graph, int v, bool visited[]) { std::queue<int> Q; Q.push(v); visited[v] = true; std::cout << graph.vertices[v].data << " "; while (!Q.empty()) { v = Q.front(); Q.pop(); EdgeNode* node = graph.vertices[v].firstedge; while (node) { int w = node->adjvex; if (!visited[w]) { Q.push(w); visited[w] = true; std::cout << graph.vertices[w].data << " "; } node = node->next; } } } ``` #### 初始化图 ```cpp int main() { int numVertices = 5; // 假设图有5个顶点 Graph g(numVertices); // 添加边，构建无向图 addEdge(g, 0, 1); addEdge(g, 0, 2); addEdge(g, 1, 3); addEdge(g, 1, 4); addEdge(g, 2, 3); addEdge(g, 3, 4); // 初始化访问状态数组 bool* visited = new bool[numVertices]; for (int i = 0; i < numVertices; ++i) { visited[i] = false; } // 执行深度优先遍历 DFS(g, 0, visited); // 清除访问状态，进行广度优先遍历 for (int i = 0; i < numVertices; ++i) { visited[i] = false; } BFS(g, 0, visited); return 0; } ``` ### 知识点总结 1. **邻接表的概念**：了解邻接表的组成结构，包括顶点表和边表。 2. **链表的操作**：掌握如何使用链表在C++中构建数据结构。 3. **图的表示方法**：理解在C++中如何通过结构体和向量（动态数组）表示图。 4. **图的遍历算法**：掌握深度优先搜索(DFS)和广度优先搜索(BFS)的基本思想和实现方法。 5. **图的添加边操作**：学习如何通过添加边来构建无向图。 以上是C++实现无向图邻接表的详细方法和操作。通过这种方式，我们可以有效地表示和操作图结构，为解决各种图相关的问题提供基础。