3

我一直在编写代码以在有向图中获取所有可能的循环。这是一个跟踪后沿的实现，只要找到一个后沿，它就会返回真，即检测到一个周期。我将其扩展到以下内容：计算树中所有可能的后边缘，后边缘的数量应该给出周期数。不确定这是否正确。使用它，我实现了以下内容： 下面的count变量没有用。最初我有它来计算每个周期的计数。但这并没有给出正确的答案。但是edgeMap存储所有后边缘的大小似乎在某些图中给出了正确的循环数，但不是全部。

该代码适用于图片中的 G2 和 G3，但不适用于 G1。（G1 只有两个周期，但我得到三个后沿）。任何关于我可能出错的建议都会有所帮助在此处输入图像描述

public int allCyclesDirectedmain(){
        clearAll();
        int count=0;
        Map<Vertex, Vertex> edgeMap = new HashMap<>();


        for (Vertex v : vertexMap.values()) {
            if (!v.isVisited && allCyclesDirected(v,edgeMap))
                count++;
        }
        System.out.println(edgeMap);
        return count;

    }
public boolean allCyclesDirected(Vertex v, Map<Vertex, Vertex> edgeMap ){
        if (!v.isVisited){
            v.setVisited(true);
            Iterator<Edge> e = v.adj.iterator();
            while (e.hasNext()){
                    Vertex t = e.next().target;
                    if (!t.isVisited && allCyclesDirected(t,edgeMap)){
                        edgeMap.put(v, t);
                            return true;
                    }
                    else 
                            return true;
                    }
                }
        return false;
    }
4

2 回答 2

3

backedges 的数量不是循环的数量，因为单个 backedge 可以参与多个循环。

在您的图 G1 中，让我们跟踪从 A 开始的深度优先搜索的进程：它访问 A->B->C，然后在 D 和 E 之间进行选择。假设它需要 D。然后它访问 E，并且找到一个去 B 的后边。事情是，EB 边同时参与了 BCE 循环和 BCDE 循环！

这是另一个例子：考虑四个节点上的完整有向图。有 12 条边，但是

  • 6个两顶点循环
  • 8个三顶点循环
  • 6个四顶点循环

总共 20 个周期 - 比图中的边还多！事实上，一个图中可以有指数级的循环数，如果 P != NP ，计算它们的问题（称为#CYCLE）在多项式时间内是不可计算的。

于 2013-11-28T04:50:34.807 回答
1

如前所述，单个后端可以在多个周期中做出贡献，因此后端的数量与周期数不同。可以使用约翰逊算法在图中找到所有简单的循环。

于 2018-09-01T18:12:12.453 回答