C++图的深度优先遍历 - 数据结构与算法可视化

图配置与控制

图类型与基本参数

选择图类型

起始顶点

图参数配置

顶点数量

边的数量

(5-15)

树深度

网格大小

动画速度

操作控制

图可视化

当前栈状态

栈顶

栈为空

未访问节点

当前节点

已访问节点

栈中节点

遍历记录

步骤	操作	节点	说明

代码执行

                                    
void DFS(Graph G, int v) {
    visited[v] = true;
    // 访问顶点v
    cout << v << " ";
    
    // 将v压入栈中
    stack.push(v);
    
    // 遍历所有邻接点
    for (int i = 0; i < G.adj[v].size(); i++) {
        int w = G.adj[v][i];
        if (!visited[w]) {
            // 递归访问未访问的邻接点
            DFS(G, w);
        }
    }
    
    // 处理完所有邻接点后，将v弹出栈
    stack.pop();
}
                                

当前步骤说明

尚未开始遍历，请点击"开始遍历"按钮。

深度优先搜索(DFS)介绍

算法原理

深度优先搜索是一种用于遍历或搜索图和树的算法，它从根节点开始，沿着一条路径尽可能深入，直到无法继续前进时回溯。

DFS算法步骤

选择起点选择一个起始顶点，并标记为已访问
深度探索对于当前顶点的每个未访问的邻接点，递归执行DFS
回溯处理当顶点的所有邻接点都处理完后，回溯到前一个顶点
继续探索重复上述过程，直到图中所有可达顶点都被访问

时间复杂度

O(V + E)

其中V为顶点数，E为边数

空间复杂度

O(V)

用于标记已访问顶点和递归调用栈

算法应用

拓扑排序

为有向无环图的顶点排序，使得所有边都从序号较小指向序号较大的顶点

路径查找

在图中查找从源顶点到目标顶点的路径

连通分量

识别图中的强连通分量或无向图中的连通分量

环检测

检测图中是否存在环路，特别是在有向图中

数据结构与算法可视化

图的深度优先遍历 (DFS)