couting后边缘来获得在有向图cylces的数目 [英] couting back edges to get the number of cylces in a directed graph

问题描述

我一直在写code以获得所有可能的循环有向图。 这里是跟踪的背面边缘的实现，每当一回边缘被发现，它返回真，一个周期被检测到。我扩展了这个以下几点： 计算在一个树中的所有可能的后边缘，的背面边缘的数量应给循环数目。不知道这是正确的。用这个，我实现了以下内容：计数下面的变量是没有用的。最初，我是有给每个周期的计数。但是，这并不给出正确的答案。但 edgeMap 的大小商店所有的后缘似乎给正确的数字在一些图表的周期，但不是全部。

I have been writing code to get all the possible cycles in a directed graph. Here is an implementation that keeps track of back edges and whenever one back edge is found, it return true that one cycle is detected. I extended this to the following: calculate all the possible back edges in a tree, the number of back edges should give the number of cycles. Not sure if this correct. using this, I implemented the following: The count variable below is not useful. Initially I had it to give the count of each cycles. but that does not give the correct answer. but the size of edgeMap that stores all the back edges seems to give the correct number of cycles in some graphs but not all.

在code适用于G2在画面的G3，但失败G1。 （G1只有两个周期，但我得到三回边）。在那里我可以去错的任何建议，将有助于

The code works for G2 an G3 in the picture, but fails for G1. (G1 has only two cycles, but I get three back edges). any suggestions of where I could be going wrong will be helpful

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

推荐答案

backedges的数没有循环的数目，因为一个单回边可以参与多于一个周期。

The number of backedges is not the number of cycles, because a single backedge can participate in more than one cycle.

在你的图G1，让我们从跟踪的深度优先搜索的发展：它访问A-> B-> C，然后有D和E之间的选择让我们假设它需要D.然后访问E，并找到一个回边去B.事情是，在EB边缘在两个BCE周期和BCDE周期的参与！

In your graph G1, let's trace the progression of the depth-first search from A: it visits A->B->C, and then has a choice between D and E. Let's suppose it takes D. Then it visits E, and finds one backedge going to B. Thing is, the EB edge participates in both the BCE cycle and the BCDE cycle!

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

Here's another example: consider the complete directed graph on four nodes. There are 12 edges, but

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

有共20个循环 - 超过有图中边！实际上，可以有一个指数在图形中循环，并计算它们的问题，所谓的#CYCLE，是不可计算在多项式时间内若P！= NP 。

for a total of 20 cycles - more than there are edges in the graph! In fact, there can be an exponential number of cycles in a graph, and the problem of counting them, called #CYCLE, is not computable in polynomial time if P != NP.

这篇关于couting后边缘来获得在有向图cylces的数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！