在有向图上进行广度优先搜索时,我很难找到正确分类边的方法。
在广度优先或深度优先搜索中,您可以将符合 4 类的边分类:
- 树
- 返回
- 交叉
- 转发
Skiena [1] 给出了一个实现。如果你沿着一条边从v1移动到v2,这里有一个在java中DFS期间返回类的方法,供引用。 parents 映射返回当前搜索的父顶点,timeOf()
方法返回顶点被发现的时间。
if ( v1.equals( parents.get( v2 ) ) ) { return EdgeClass.TREE; }
if ( discovered.contains( v2 ) && !processed.contains( v2 ) ) { return EdgeClass.BACK; }
if ( processed.contains( v2 ) )
{
if ( timeOf( v1 ) < timeOf( v2 ) )
{
return EdgeClass.FORWARD;
}
else
{
return EdgeClass.CROSS;
}
}
return EdgeClass.UNCLASSIFIED;
我的问题是我无法正确地对有向图进行广度优先搜索。例如:
下图 - 这是一个循环 - 没问题:
A -> B
A -> C
B -> C
BFSing从A开始,B会被发现,然后C。边eAB和eAC是TREE边,当最后交叉eBC时,B和C被处理和发现,这条边被正确地归类为CROSS。
但是普通循环不起作用:
A -> B
B -> C
C -> A
当边缘 eCA 最后被越过时,A 被处理并被发现。所以这条边被错误地标记为CROSS,是否应该是BACK边。
这两种情况的处理方式确实没有区别,即使两条边的类别不同。
如何在有向图上为 BFS 实现正确的边分类?
编辑
这里是从@redtuna 答案派生的实现。 我刚刚添加了一个检查以不获取根的父级。 我有 JUnits 测试表明它适用于有向图和无向图,在循环、直线、 fork 、标准示例、单边等的情况下......
@Override
public EdgeClass edgeClass( final V from, final V to )
{
if ( !discovered.contains( to ) ) { return EdgeClass.TREE; }
int toDepth = depths.get( to );
int fromDepth = depths.get( from );
V b = to;
while ( toDepth > 0 && fromDepth < toDepth )
{
b = parents.get( b );
toDepth = depths.get( b );
}
V a = from;
while ( fromDepth > 0 && toDepth < fromDepth )
{
a = parents.get( a );
fromDepth = depths.get( a );
}
if ( a.equals( b ) )
{
return EdgeClass.BACK;
}
else
{
return EdgeClass.CROSS;
}
}
最佳答案
How do you implement a proper edge classification for a BFS on a directed graph?
正如您已经建立的那样,第一次看到一个节点会创建一个树边。正如 David Eisenstat 在我之前所说的那样,BFS 而不是 DFS 的问题在于,无法仅根据遍历顺序将后边与交叉边区分开来。
相反,您需要做一些额外的工作来区分它们。正如您将看到的,关键是使用交叉边的定义。
最简单(但内存密集型)的方法是将每个节点与其前任集合相关联。当您访问节点时,这可以轻松完成。当找到节点 a 和 b 之间的非树边时,考虑它们的前导集。如果一个是另一个的真子集,那么你就有了后边。否则,它就是交叉边。这直接来自交叉边的定义:它是节点之间的边,树上既不是对方的祖先也不是对方的后代。
更好的方法是只将“深度”数字与每个节点而不是集合相关联。同样,这在您访问节点时很容易完成。现在,当您在 a 和 b 之间找到非树边时,从两个节点中较深的节点开始,然后沿着树边向后移动,直到回到与另一个节点相同的深度。因此,例如假设 a 更深。然后你重复计算 a=parent(a) 直到 depth(a)=depth(b)。
如果此时 a=b 那么您可以将该边分类为后边,因为根据定义,其中一个节点是树上另一个节点的祖先。否则,您可以将其归类为交叉边,因为我们知道这两个节点都不是另一个节点的祖先或后代。
伪代码:
foreach edge(a,b) in BFS order:
if !b.known then:
b.known = true
b.depth = a.depth+1
edge type is TREE
continue to next edge
while (b.depth > a.depth): b=parent(b)
while (a.depth > b.depth): a=parent(a)
if a==b then:
edge type is BACK
else:
edge type is CROSS
关于algorithm - 有向图广度优先搜索期间的边分类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29631211/