C++邻接矩阵图存储与遍历详解：BFS & DFS实例

本文主要介绍了如何在C++中利用邻接矩阵实现图的数据结构，并结合广度优先搜索(BFS)和深度优先搜索(DFS)算法进行图的遍历。首先，我们通过邻接矩阵的方式来表示图，邻接矩阵是一种二维数组，其中每个元素`edge[i][j]`表示顶点i和顶点j之间是否存在边。在这个例子中，定义了一个名为`GRAPH`的结构体，包含顶点数组`vex`，邻接矩阵`edge`，顶点数`n`，以及边数`e`。 在`Create`函数中，创建一个图并根据输入的边的信息填充邻接矩阵。例如，对于输入的`011`表示顶点0与顶点1之间有一条边，`021`表示顶点0与顶点2之间有一条边，依此类推。邻接矩阵的索引通常从0开始，所以这些边在矩阵中的位置是`edge[0][1]`和`edge[0][2]`。 接下来，`BFS`函数实现了广度优先遍历。它使用一个队列来存储待访问的节点，初始时前驱和后继指针`front`和`rear`分别设为-1。遍历过程从起点`k`开始，将起点入队，然后循环处理队列中的节点，直到队列为空。对于每个节点，标记为已访问，并将它的邻居（邻接矩阵对应位置的节点）加入队列，继续扩展搜索范围。 `DFS`函数则实现了深度优先遍历，它使用一个访问标记数组`visited`来跟踪节点是否被访问过。同样从起点`k`开始，如果节点未被访问，则递归地访问其所有相邻节点，直到遍历完所有路径或无法再继续为止。 `main`函数中，首先初始化访问标记数组，然后调用`Create`函数构建图，可以选择先执行`BFS`或`DFS`。在本例中，最后选择了`DFS`。 总结来说，本文通过C++编程展示了如何用邻接矩阵数据结构表示图，并演示了如何使用广度优先搜索和深度优先搜索算法进行图的遍历。这对于理解和实践图论中的基本概念，以及在实际编程中处理网络关系问题非常有帮助。通过这两个算法，可以找出最短路径、发现连通分量等图的特性。