tree - 树边缘和前向边缘之间的区别

Question

当我遇到这个问题时，我正在读一本书：当在图形上运行 DFS 时，如何从图中特定顶点的发现和完成时间来区分前向边和树边之间的区别？

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

但是，我无法开发一种算法，也怀疑这种方法有问题。请帮帮我。谢谢你。

Answer 1

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

1. 如果从 u 访问一个新节点 v（v 之前没有被发现），
   则 (u,v) 是树边。

2. 否则，如果我们访问之前已经访问过的节点 v

   • 如果我们还没有离开/结束那个节点（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++;

}

Answer 2

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