algorithm - 无向图中的前向边

Question

CLRS - 第 22 章

Theorem 22.10

In a depth-first search of an undirected graph G, every edge of G is either a tree edge or a back edge.

Proof Let (u,v) be an arbitrary edge of G, and suppose without loss of generality that u.d < v.d. Then the search must discover and finish v before it finishes u (while u is gray), since v is on u’s adjacency list. If the first time that the search explores edge (u,v), it is in the direction from u to v, then v is undiscovered (white) until that time, for otherwise the search would have explored this edge already in the direction from v to u. Thus, (u.v) becomes a tree edge. If the search explores (u,v) first in the direction from v to u, then (u,v) is a back edge, since u is still gray at the time the edge is first explored.

我当然理解证明；但不太相信前沿的想法。

在上图中，从第一个顶点到第三个顶点(第一行)有一条前向边。第一个顶点是源。

据我所知，DFS(S) 将包含一个前向顶点 1 -> 3。(我显然错了，但我需要有人来纠正我!)

Answer 1

您似乎没有包含“前沿”的定义，所以我将从我学到的定义开始。

Assuming u.d < v.d, DFS labels the edge (u,v) a forward edge if when crossing the edge from u to v, v has already been marked as visited.

尽管如此，我声明在无向图中不能有前向边。

为了反驳，假设这是可能的。因此，目标节点已被标记为已访问。因此，DFS 已经到达那里并跨越了所有相邻的边缘。特别是，您必须已经在相反的方向越过该边缘。因此，边缘已经被标记为某种类型的边缘，因此不会被标记为“前向边缘”。

因此，前向边只能出现在有向图中。

---

现在，以防万一您混淆了“前向边缘”和“树状边缘”，您描述的边缘仍然不一定是树状边缘。如果穿越时是您第一次访问目标节点，则它只是一个树边。在无向图中考虑它的简单方法是，当您遍历一条边时，如果已经到达目标节点，则它是一条后向边，否则就是一条树边。