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

Question

我在看书的时候遇到了这个问题: 当在图中运行 DFS 时，如何从图中特定顶点的发现时间和完成时间来区分前向边和树边之间的差异？

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

但是，我无法开发一种算法，并且也怀疑这种方法是否有缺陷。请帮帮我。谢谢。

Answer 1

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

1. 如果从 u 访问新节点 v(v 之前未被发现)
   比 (u,v) 是树边。

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

   • 如果我们还没有离开/完成该节点(v)，那么 v 肯定是 u 的祖先和 (u,v) 后边缘。

   • 否则，有两种可能性 - 横向边缘或前向边缘。在这两种情况下，我们都会访问已经离开的节点(v)。所以在这里， 我们可以通过到达时间来区分它们。

     • 它是一个前向边缘(从祖先到后代，u -> v)， 如果你的到达时间会少于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++;

}