有向图广度优先搜索期间的边分类

Question

在有向图上进行广度优先搜索时，我很难找到正确 class 化边的方法。

在广度优先或深度优先搜索中，您可以class确定满足 4 classes 的边：

树
返回
交叉
前进

Skiena [1] 给出了一个实现。如果你沿着一条边从v1移动到v2，这里有一个在java的DFS期间return the class的方法，供参考。 parents 映射 returns 当前搜索的父顶点，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

BFS从A开始，B会被发现，然后C。边eAB和eAC是TREE边，最后穿过eBC时，处理发现B和C，这条边妥当class化为交叉。

但是普通循环不起作用：

A -> B B -> C C -> A

当边缘eCA最后被越过时，A被处理并被发现。所以这条边被错误地标记为CROSS，是否应该是BACK边。

两种情况的处理方式确实没有区别，即使两条边有不同的classes。

如何在有向图上为 BFS 实现适当的边 class化？

[1] http://www.algorist.com/

编辑

这里是从@redtuna 答案派生的实现。我刚刚添加了一个检查以不获取根的父级。我有 JUnits 测试表明它适用于有向图和无向图，在循环、直线、叉子、标准示例、单边等的情况下....

@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; } }

Answer 1

这里DFS的关键属性是，给定两个节点u和v，区间[u.discovered，u.processed]是[v.discovered的子区间, v.processed] 当且仅当 u 是 v 的后代。 BFS 中的时间没有这个属性;您必须做其他事情，例如，通过 BFS 生成的树上的 DFS 计算间隔。那么分类伪代码是 1. 检查树中的成员（树边） 2. 检查头部的区间是否包含尾部的（后边） 3. 检查尾部的区间是否包含头部的（前向边） 4. 否则，声明交叉边。

Answer 2

How do you implement a proper edge classification for a BFS on a directed graph?

正如您已经建立的那样，第一次看到一个节点会创建一个树边。正如 David Eisenstat 在我之前所说的那样，BFS 而不是 DFS 的问题在于，无法仅根据遍历顺序将后边与交叉边区分开来。

相反，您需要做一些额外的工作来区分它们。正如您将看到的，关键是使用交叉边的定义。

最简单（但占用大量内存）的方法是将每个节点与其前任节点集相关联。当您访问节点时，这可以轻松完成。当找到节点 a 和 b 之间的非树边时，考虑它们的前导集。如果一个是另一个的真子集，那么你就有了后边。否则，它就是交叉边。这直接来自交叉边的定义：它是节点之间的边，树上既不是对方的祖先也不是对方的后代。

更好的方法是只将一个 "depth" 数字与每个节点相关联，而不是与一个集合相关联。同样，这在您访问节点时很容易完成。现在，当您在 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

Answer 3

而不是 timeof()，您需要另一个顶点属性，它包含到根的距离。让命名为 distance。

您必须按以下方式处理 v 个顶点：

for (v0 in v.neighbours) {
    if (!v0.discovered) {
        v0.discovered = true; 
        v0.parent = v;
        v0.distance = v.distance + 1;
    }
}
v.processed = true;

在你处理了一个v顶点后，你可以运行对[=14的每条边（从v1到v2）使用下面的算法=]:

if (!v1.discovered) return EdgeClass.BACK;  
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS;
else if (v1.distance > v2.distance) return EdgeClass.BACK;
else {
    if (v2.parent == v1) return EdgeClass.TREE;
    else return EdgeClass.FORWARD;
}

有向图广度优先搜索期间的边分类

Edge classification during Breadth-first search on a directed graph

algorithm

graph-theory

graph-algorithm

breadth-first-search

directed-graph