couting back edges得到有向图中的圆柱数

我一直在编写代码以获得有向图中所有可能的周期。 Here是一种实现方式，可以跟踪后沿，并且每当找到一个后沿时，它就会返回检测到一个周期的结果。我将其扩展到以下内容：计算树中所有可能的后边，后边数应该给出循环数。不知道这是否正确。使用这个，我实现了以下内容：下面的count变量没有用。最初，我已经给它每个周期的计数。但是这并没有给出正确的答案。但存储所有后边的edgeMap的大小似乎在某些图中给出正确的周期数，但不是全部。couting back edges得到有向图中的圆柱数

该代码适用于图片中的G2和G3，但G1代码失败。（G1只有两个周期，但我有三个后沿）。在那里我可以会错误的任何建议，将有助于 enter image description here

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

来源

2013-11-27 eagertoLearn

我想你已经在寻找一些已知解决方案的不平凡的问题。你看过以前的答案吗？例如：http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph其中的一个答案提到了Java中用于计算循环的算法：http：//normalisiert.de/code/ java/elementaryCycles.zip –

@Ricardo：我看着它。这不是微不足道的，我同意。 Himadri Choudhury提供的链接上有一个帖子。这个解决方案看起来很优雅，但不清楚，我在那里留下了一个便条，但没有人回答。 –

backedges的数量不是周期数，因为一个回边可以参加一个以上的周期。

在你的图G1中，让我们追踪深度优先搜索的进展：A：它访问A-> B-> C，然后在D和E之间进行选择。假设它需要D.然后它访问E，并发现一个backedge转到B.事情是，EB边缘参与BCE循环和BCDE循环！

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

6两顶点周期
8三顶点周期
6四顶点周期

总共20个循环的 - 超过有图中的边缘！实际上，图中可能存在指数周期数，并计算它们的问题，称为#CYCLE，is not computable in polynomial time if P != NP。

来源

2013-11-28 04:50:34

couting back edges得到有向图中的圆柱数

回答

相关问题