深度优先搜索

图的深度优先遍历(或搜索)类似于树的深度优先遍历。这里唯一的问题是,与树不同,图形可能包含循环,因此我们可能会再次来到同一节点。为避免多次处理节点,我们使用布尔访问数组。

下面的算法介绍了使用 DFS 进行图遍历的步骤:

算法 DFS(v);

输入 :图中的顶点 v

输出 :边缘标记为发现边缘和后备

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

https://i.stack.imgur.com/Nxxfb.jpg

https://i.stack.imgur.com/TtAu7.jpg