树边缘和正向边缘之间的区别
当我遇到此问题时,我正在阅读一本书: 如何从DFS中的特定顶点的发现和完成时间中区分正向边和树边?在它上面运行?树边缘和正向边缘之间的区别
我到目前为止所尝试的是:Fwd之间的主要区别。并且树边缘是如果在A和B之间存在树边缘,则A是B的直接邻居,其路径长度为1,但是如果是Fwd。边缘,那么路径长度应该大于1左右。因此,当分析可以存储在数组中的发现和完成时间时,我们可以检查它们的完成时间/开始时间是否相差1。因为如果它们这样做,那么它就是树边缘,否则就是前沿。
但是,我无法开发算法,也怀疑这种方法是一个错误的方法。请帮助我。谢谢。
虽然这样做有向图的深度优先搜索,
如果访问一个新节点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++;
}
如果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)行)包括在一起。