树边和前向边的区别

Question

我正在看书的时候遇到了这个问题：当 DFS 为运行时，如何根据图中特定顶点的发现时间和完成时间区分前向边和树边？

到目前为止，我尝试过的是：Fwd 之间的主要区别。和 Tree Edges 是，如果 A 和 B 之间存在树边，则 A 是 B 的直接邻居，路径长度为 1，但如果是 Fwd。边，那么路径长度应该大于1左右。因此，在分析可以存储在数组中的发现和完成时间时，我们可以检查它们的 finish/start 时间是否相差 1。因为如果相差 1，那么它就是树边，否则就是前向边。

但是，我无法开发算法，也怀疑这种方法是否存在问题。请帮帮我。谢谢。

Answer 1

如果在 v 的观察时间已经定义了 discoveryTime(v) 并且 discoveryTime(u) <= discoveryTime(v)，则边 (u, v) 被分类为前向边。因此，边 (u, u) 也被归类为前向边。分类基于 DFS 遍历顶点的顺序，即从另一个顶点开始可能会导致不同的分类。伪代码的算法（有解释和证明）可以在书 Kurt Mehlhorn: Data Structures and Efficient Algorithms, Volume 2, Springer Verlag, EATCS Monographs, 1984.（绝版但作者在线提供）第 4 章，"Algorithms on Graphs"，第 21 页中找到，如下所示.我已将第 25 页上的片段包含在边缘分类中（第 (8) 至 (10) 行，如作者所建议的）。

Answer 2

在有向图上进行深度优先搜索时，

如果从u
访问一个new节点v（v之前没有被发现）比 (u,v) 是树边。
否则如果我们访问之前已经访问过的节点 v
- 如果我们还没有 departed/finished 来自该节点 (v)，那么 v 肯定是 u 的祖先和 (u,v) 后缘。
- 否则，有两种可能——跨边或前边。在这两种情况下，我们都访问了我们已经离开的节点 (v)。所以在这里，我们可以通过到达时间来区分它们。
  - 它是一个前缘（从祖先到后代，u -> v），如果 u 的到达时间会小于 v
  - 是跨边，如果u的到达时间会大于v。

供参考：

void dfsEdges(struct graph*G, int v, int *visited, int *arrTime, int *depTime)
{
 static int time=0;


visited[v]=1;
arrTime[v]=time++;

struct node *temp = G->array[v];
while(temp!=NULL)
{
    if(visited[temp->val] != 1)
    {
        dfsEdges(G,temp->val,visited,arrTime,depTime);
    }
    else
    {
        if(depTime[temp->val] ==-1)
        printf("\n%d - %d is back edge\n",v,temp->val);
        else
        {
            if(arrTime[v]<arrTime[temp->val])
            printf("\n%d - %d is forward edge\n",v,temp->val);
            else
            printf("\n%d - %d is cross edge\n",v,temp->val);
        }

    }
    temp=temp->next;

}
depTime[v]=time++;

}

树边和前向边的区别

Difference between Tree Edges and Forward Edges

tree

depth-first-search

graph-traversal

graph-algorithm