图的遍历：邻接矩阵与邻接表实现

本文将介绍如何使用邻接矩阵和邻接表两种数据结构来实现图的遍历。邻接矩阵适用于表示稠密图，邻接表则更适合稀疏图。我们将首先理解这两种数据结构，然后分别探讨它们在图遍历中的应用。 在图的遍历中，我们通常需要访问图中的每一个顶点及其相邻的边。遍历方法包括深度优先搜索（DFS）和广度优先搜索（BFS）。 **邻接矩阵** 是一种二维数组，用于表示图中顶点之间的邻接关系。如果图是无向的，邻接矩阵是对称的；如果是有向的，矩阵可能不对称。在邻接矩阵中，元素值表示对应顶点之间是否存在边以及边的权重。对于无权图，非零值通常表示存在边，全零矩阵表示空图。在邻接矩阵中进行DFS或BFS，可以直接通过矩阵元素访问相邻顶点。 **邻接表** 是一种链式存储结构，它为每个顶点维护一个链表，链表中的节点代表与该顶点相连的所有边。邻接表适合表示稀疏图，因为它可以节省大量空间。在邻接表中进行DFS或BFS，需要遍历每个顶点的链表来找到相邻顶点。 代码示例中定义了`MGraph`结构体，用于存储邻接矩阵表示的图。`AdjMatrix`是一个二维数组，`vexs`存储顶点信息，`vexnum`和`arcnum`分别记录顶点数和边数，`kind`表示图的类型（无向图、有向图等）。 `LocateVex`函数用于查找指定顶点在数组中的位置，`FirstAdjVex`和`NextAdjVex`用于获取一个顶点的第一个和下一个相邻顶点。`CreateUDN`函数创建了一个无向图，用户输入顶点数、边数以及每条边的两个顶点和权重。 在实现图遍历时，DFS通常使用递归方式，从一个顶点出发，访问其所有未访问过的邻接顶点，然后再对这些顶点进行同样的操作，直到所有顶点都被访问过。BFS则使用队列，先访问起始顶点，然后将其所有邻接顶点入队，再依次访问队首的邻接顶点并入队它们的邻接顶点，如此循环，直至队列为空。 在邻接矩阵中，DFS和BFS的时间复杂度都是O(V+E)，因为每个顶点和每条边都会被访问一次。而在邻接表中，由于只存储了实际存在的边，所以时间复杂度通常是O(V+E)，但在稀疏图中，这个时间复杂度接近O(V)。 总结来说，邻接矩阵和邻接表是两种常见的图存储结构，它们各有优缺点。邻接矩阵实现简单，但空间效率较低；邻接表空间效率高，但操作稍显复杂。在实际应用中，应根据图的特性选择合适的数据结构。