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

Question

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

在广度优先或深度优先搜索过程中,可以将遇到的边缘分为4类：

• 树
• 后退
• 交叉
• 转发

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

但普通循环不起作用：

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

当最后交叉边eCA时，处理并发现A。所以这个边被错误地标注为十字，是否应该是一个后边。

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

@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

如何为有向图上的BFS实现正确的边分类？

正如您已经建立的，第一次看到一个节点会创建一个树边缘。用BFS而不是DFS的问题，正如David Eisenstat在我前面所说的那样，仅仅根据遍历顺序不能区分后边和交叉边。

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

  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