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