图数据结构：C++实现邻接表与邻接矩阵

在计算机科学中，图的表示是一个基础问题，它直接关系到图算法的效率和实现。图可以通过多种方式表示，其中最常见的是邻接矩阵和邻接表。这两种表示方法各有优缺点，在不同的应用场景下有不同的效率表现。 ### 邻接矩阵表示 邻接矩阵是一个二维数组，用来表示图中所有顶点之间的连接关系。对于有n个顶点的图，邻接矩阵是一个n×n的二维数组，数组中的每个元素用来表示两个顶点之间是否存在一条边。如果顶点i和顶点j之间有边相连，则邻接矩阵中的元素A[i][j]通常被设置为1（或边的权重，如果没有权重则为0）；如果没有边连接，则设置为0（或无穷大，如果图是加权的，用来表示不存在连接）。 #### 特点： - **空间复杂度**：邻接矩阵的空间复杂度是O(n^2)，因此它不适用于稀疏图，但对于稠密图来说，由于直接通过二维数组的索引可以快速找到任意两个顶点之间的连接状态，因此效率较高。 - **时间复杂度**：在邻接矩阵中查找两个顶点是否相邻的时间复杂度是O(1)。 - **对称性**：无向图的邻接矩阵是对称的，即A[i][j] = A[j][i]。 ### 邻接表表示 邻接表是一种链式存储结构，它更适合表示稀疏图。每个顶点用一个节点表示，节点中包含顶点信息和一个指向所有邻接顶点的链表。如果图是有向的，则链表中的元素是该顶点的后继顶点；如果是无向的，则链表中的元素是该顶点的邻接顶点。 #### 特点： - **空间复杂度**：邻接表的空间复杂度是O(n+m)，其中n是顶点数，m是边数，因此它适用于表示稀疏图。 - **时间复杂度**：在邻接表中查找两个顶点是否相邻的时间复杂度是O(n)，其中n是顶点数。 - **链表结构**：由于是链式存储，添加和删除边的操作在邻接表中更为灵活和高效。 ### C++实现 在C++中实现图的邻接矩阵和邻接表表示，需要考虑如何定义顶点、边以及图的基本操作，如添加/删除顶点和边、遍历等。 #### 邻接矩阵的C++实现： ```cpp const int MAX_VERTICES = 100; // 最大顶点数 int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵 void initializeGraph(int numVertices) { for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { adjMatrix[i][j] = 0; // 初始化为0，无连接 } } } void addEdge(int start, int end) { adjMatrix[start][end] = 1; // 有向图或无向图的添加 // 如果是无向图，还需要添加： // adjMatrix[end][start] = 1; } ``` #### 邻接表的C++实现： ```cpp struct Vertex { int data; Vertex* next; }; struct Graph { Vertex* vertices; int numVertices; }; void addEdge(Graph& graph, int src, int dest) { // 添加一条从src到dest的边 Vertex* newVertex = new Vertex; newVertex->data = dest; newVertex->next = graph.vertices[src].next; graph.vertices[src].next = newVertex; // 如果是无向图，则还需要添加反向边 } void initializeGraph(Graph& graph, int numVertices) { graph.vertices = new Vertex[numVertices]; graph.numVertices = numVertices; for (int i = 0; i < numVertices; i++) { graph.vertices[i].data = i; graph.vertices[i].next = nullptr; } } ``` ### 优缺点总结 - 邻接矩阵适合用于稠密图，便于快速判断任意两个顶点的邻接关系，缺点是空间消耗大。 - 邻接表适合用于稀疏图，节省空间，但需要遍历链表来判断顶点的邻接关系，效率相对较低。 - 在实际应用中，根据图的稠密程度和频繁操作（如查询边、添加边等）来选择合适的图表示方法。 从标题和描述中提供的信息来看，这段代码的实现应当包含上述提到的邻接矩阵和邻接表的定义、初始化以及对边的操作等基础功能。此外，代码还可能包括图的遍历算法（如深度优先搜索和广度优先搜索），以及根据题目的不同要求，可能实现的其他高级功能。运行界面效果好则可能意味着代码在图形用户界面上有一定的实现，或者在控制台上提供了友好的交互方式。