5

CLRS - 第 22 章

定理 22.10

在无向图 G 的深度优先搜索中，G 的每条边要么是树边，要么是后边。

证明 假设 (u,v) 是 G 的任意边，并且不失一般性地假设 ud < vd 那么搜索必须在完成 u 之前发现并完成 v（而 u 是灰色的），因为 v 在 u 的邻接表上. 如果搜索第一次探索边缘 (u,v)，它是在从 u 到 v 的方向上，那么在那个时间之前 v 是未被发现的（白色），否则搜索将已经在从v 给你。因此，(uv) 变成了树的边缘。如果搜索首先沿从 v 到 u 的方向探索 (u,v)，则 (u,v) 是后边缘，因为在第一次探索边缘时 u 仍然是灰色的。

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

无向图

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

据我了解，DFS(S) 将包括一个前向顶点 1 -> 3。（我显然错了，但我需要有人来纠正我！）

4

3 回答 3

4

It looks like you didn't include the definition of "forward edge," so I'll start with the definition I learned.

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.

Because of that though, I claim that you cannot have forward edges in an undirected graph.

Assume for the sake of contradiction that it was possible. Therefore, the destination node is already marked as visited. Thus, DFS has already gone there and crossed all of the adjacent edges. In particular, you had to have already crossed that edge in the opposite direction. Thus, the edge has already been marked as a certain type of edge and thus won't be marked as a "forward edge".

Because of this, forward edges can only occur in directed graphs.

Now, just in case you mixed up "forward edges" and "tree edges", the edge you describe still isn't necessarily a tree edge. It is only a tree edge if when crossing, that was the first time you've visited the destination node. The easy way to think about it in undirected graphs is that when you traverse an edge, it is a back edge if the destination node has been reached already, and a tree edge otherwise.

于 2013-11-10T07:42:50.640 回答
0

在一般图的 DFS 树中，有 TREE、FORWARD、BACK 和 CROSS 边。

在无向图的 DFS 树中，可能的 FORWARD 边被标记为 BACK 边。可能的交叉边被标记为树边。

在这两种情况下，原因是边缘可以在两个方向上遍历，但是您首先遇到它们是 BACK 和 TREE，第二次遇到它们是 FORWARD 并且可能是 CROSS 并且它们已经被标记。

从某种意义上说，一条边既是 FORWARD 又是 BACK，既可以是 CROSS 也可以是 TREE，但首先找到的边分别是 BACK 和 TREE。

于 2013-11-10T09:58:46.267 回答
0

我相信您缺少的是关于算法访问不同顶点的顺序的一些假设。

让我们假设算法按字典顺序访问顶点。让我们这样命名顶点：

 -------
|       |
S - A - B
|   |   |
C - D - E

在这种情况下，前边缘将是S->A, A->B, B->E, E->D, D->C。其余的边缘是后边缘。

现在让我们重命名图表：

 -------
|       |
S - B - A
|   |   |
C - D - E

在这种情况下，前向边将是S->A, A->B, B->D, D->C, D->E（注意S->A和S->B与前面的例子中的边不同）。

如您所见，输出取决于算法选择顶点的顺序。当图形是匿名的时，任何输出都可能是正确的。

于 2013-11-10T07:48:34.107 回答