树边缘和正向边缘之间的区别

当我遇到此问题时，我正在阅读一本书：如何从DFS中的特定顶点的发现和完成时间中区分正向边和树边？在它上面运行？树边缘和正向边缘之间的区别

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

但是，我无法开发算法，也怀疑这种方法是一个错误的方法。请帮助我。谢谢。

来源

2015-03-31 Cartoon

虽然这样做有向图的深度优先搜索，

如果访问一个新节点V（V还没有被发现之前）从u
比（u，v）是树的边缘。
否则，如果我们访问一个节点U已经访问过的早期
- 如果我们还没有离开/从该节点完成（V），比肯定v是 ü的祖先和（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++; 

}

来源

2015-04-28 09:32:43

如果discoveryTime（v）已经在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章，“图上的算法”，第21页，如下所示。我已经将第25页的片段与边缘分类（作者提议的第（8）至（10）行）包括在一起。

来源

2015-04-20 13:31:26 stephan

树边缘和正向边缘之间的区别

回答

相关问题