深度与广度遍历图算法详解及实现

"图的深度优先遍历和广度优先遍历是图论中的两种基本遍历算法，用于访问图中的所有顶点。这两种方法在数据结构和算法领域有着广泛的应用，例如在解决迷宫问题、拓扑排序、查找连通性等场景。" 深度优先遍历（DFS, Depth First Search）是一种自底向上的搜索策略，从起始顶点开始，沿着某一分支尽可能深地探索，直到到达叶子节点，然后回溯到上一个顶点，选择下一个未访问的分支进行探索，直到所有顶点都被访问。DFS通常使用栈或者递归实现。在无环图中，DFS可以用于判断图的连通性。在有环图中，DFS可以检测环的存在。 广度优先遍历（BFS, Breadth First Search）是一种自顶向下的搜索策略，从起始顶点开始，先访问与其相邻的所有顶点，然后再访问这些相邻顶点的相邻顶点，直到所有顶点都被访问。BFS通常使用队列来存储待访问的顶点。在无环图中，BFS可以找到两个顶点之间的最短路径（如果边的权重都是1）。在有环图中，BFS同样可以判断连通性。 在C++中，我们可以用以下方式实现这两种遍历： 对于DFS，可以使用递归的方式实现： ```cpp void DFS(MGraph G, int v) { static bool visited[MAX_VERTEX_NUM] = {false}; visited[v] = true; cout << G.vexs[v] << " "; for (int i = 0; i < G.vexnum; i++) { if (!visited[i] && G.arcs[v][i] == 1) { DFS(G, i); } } } ``` 而对于BFS，可以使用队列来实现： ```cpp void BFS(ALGraph G, int s) { Queue Q; // 定义一个队列 bool visited[MAX_VERTEX_NUM] = {false}; visited[s] = true; Q.enQueue(s); // 将起始顶点入队 while (!Q.isEmpty()) { int u = Q.deQueue(); // 出队并访问 cout << G.vertices[u].data << " "; ArcNode *p = G.vertices[u].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { visited[p->adjvex] = true; Q.enQueue(p->adjvex); } p = p->nextarc; } } } ``` 上述代码中的`MGraph`和`ALGraph`分别代表邻接矩阵和邻接表两种表示图的方式，`LocateVex`函数用于查找顶点在图中的位置，`Queue`则表示链式队列。 在实际应用中，选择DFS还是BFS取决于具体问题的需求。DFS适用于空间效率优先且不关心访问顺序的情况，而BFS则适用于寻找最短路径或者按距离顺序访问顶点的场景。理解并掌握这两种遍历算法是数据结构和算法学习的重要部分，它们有助于解决各种复杂的问题。