在有向图的广度优先搜索中进行边分类

Question

我在进行有向图的广度优先搜索时，遇到了正确分类边的困难。

在进行广度优先或深度优先搜索期间，您可以将遇到的边分为4类：

• TREE（树边）
• BACK（返祖边）
• CROSS（横叉边）
• FORWARD（前向边）

Skiena [1] 给出了实现方法。如果您沿着从v1到v2的边移动，在Java中有一种方法可以返回DFS期间的边类型（用于参考）。parents map 返回当前搜索的父顶点，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;

我的问题是，我无法正确地执行有向图上的BFS（广度优先搜索）。例如：

以下循环图是可以的：

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

BFS 从 A 开始，会先发现 B，然后是 C。边 eAB 和 eAC 是 TREE edges，在穿过 eBC 最后一次时，B 和 C 被处理并被发现，这条边被正确地分类为 CROSS。

但普通的循环不起作用：

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

当最后穿过边eCA时，A被处理并被发现。因此，这条边被错误地标记为CROSS，而实际上它应该是一条BACK边。

即使两条边具有不同的类别，处理这两种情况的方法确实没有区别。

如何在有向图上实现BFS的适当边分类？

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

}

- Jean-Yves

Answer 1

如何在有向图上实现BFS的适当边分类？ 正如您已经确定的那样，第一次看到一个节点会创建一条树边。 如David Eisenstat在我之前所说的那样，与DFS不同，BFS的问题在于无法仅基于遍历顺序区分回边和交叉边。 相反，您需要做一些额外的工作来区分它们。 正如您将看到的那样，关键是使用交叉边的定义。 最简单（但内存密集）的方法是将每个节点与其前任集合关联起来。 这可以在访问节点时轻松完成。 在找到节点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

- redtuna

---

我已经成功地实现并测试了这个解决方案。它可以在有向/无向图的情况下正常工作。我进行了一些小的更改，将在问题下面发布。谢谢！ - Jean-Yves

Answer 2

DFS的关键属性在于，给定两个节点u和v，当且仅当u是v的后代时，[u.discovered，u.processed]间隔是[v.discovered，v.processed]间隔的子间隔。BFS中的时间没有这个属性；您需要执行其他操作，例如通过BFS生成的树上的DFS计算间隔。然后，分类伪代码为1.检查是否属于树（树边）2.检查头部的间隔是否包含尾部的（反向边）3.检查尾部的间隔是否包含头部的（正向边）4.否则，声明交叉边。

- David Eisenstat

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的顶点之后，你可以对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;
}

- Zsolt Mester

---

嘿，谢谢Zsolt！我一直在实现我收集到的3个答案。对于你的答案，我想我有一个反例。考虑一个钻石形： A-B， A-C， B-D， C-D BFS将遍历A、B、C和D。最后一条经过的边是eCD，被错误地分类。此时发现并处理了C，发现但未处理D。它们的距离不同，dD > dC。因此，它被错误地分类为FORWARD边，但它是CROSS边。 - Jean-Yves