我如何才能找到(遍历)有向图中从/到给定节点的所有周期?

例如,我想要这样的东西:

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

而不是: B - > C > B


当前回答

首先,你并不是真的想要找出所有的循环因为如果有1个,那么就会有无穷多个循环。比如A-B-A, A-B-A- b - a等等。或者可以将2个循环组合成一个8-like循环等等……有意义的方法是寻找所有所谓的简单循环——那些除了开始/结束点之外不交叉的循环。如果你愿意,你可以生成简单循环的组合。

One of the baseline algorithms for finding all simple cycles in a directed graph is this: Do a depth-first traversal of all simple paths (those that do not cross themselves) in the graph. Every time when the current node has a successor on the stack a simple cycle is discovered. It consists of the elements on the stack starting with the identified successor and ending with the top of the stack. Depth first traversal of all simple paths is similar to depth first search but you do not mark/record visited nodes other than those currently on the stack as stop points.

The brute force algorithm above is terribly inefficient and in addition to that generates multiple copies of the cycles. It is however the starting point of multiple practical algorithms which apply various enhancements in order to improve performance and avoid cycle duplication. I was surprised to find out some time ago that these algorithms are not readily available in textbooks and on the web. So I did some research and implemented 4 such algorithms and 1 algorithm for cycles in undirected graphs in an open source Java library here : http://code.google.com/p/niographs/ .

顺便说一句,因为我提到了无向图:它们的算法是不同的。构建一棵生成树,然后每一条不属于树的边与树中的一些边一起形成一个简单的循环。这样发现的循环形成了所谓的循环基。所有的简单循环都可以通过组合两个或多个不同的基循环来找到。更多细节请参见:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。

其他回答

我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·b·约翰逊(Donald B. Johnson),可以在以下链接中找到:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

java实现可以在下面找到:

http://normalisiert.de/code/java/elementaryCycles.zip

约翰逊算法的Mathematica演示可以在这里找到,实现可以从右边下载(“下载作者代码”)。

注:实际上,这个问题有很多算法。本文列举了其中一些:

http://dx.doi.org/10.1137/0205007

根据文章,Johnson的算法是最快的。

澄清:

Strongly Connected Components will find all subgraphs that have at least one cycle in them, not all possible cycles in the graph. e.g. if you take all strongly connected components and collapse/group/merge each one of them into one node (i.e. a node per component), you'll get a tree with no cycles (a DAG actually). Each component (which is basically a subgraph with at least one cycle in it) can contain many more possible cycles internally, so SCC will NOT find all possible cycles, it will find all possible groups that have at least one cycle, and if you group them, then the graph will not have cycles. to find all simple cycles in a graph, as others mentioned, Johnson's algorithm is a candidate.

从开始节点s开始的DFS,在遍历过程中跟踪DFS路径,如果在到s的路径中发现从节点v开始的边,则记录该路径。(v,s)是DFS树中的后边,因此表示包含s的周期。

我无意中发现了下面的算法,它似乎比Johnson的算法更有效(至少对于更大的图)。然而,与Tarjan的算法相比,我不确定它的性能如何。 此外,到目前为止,我只检查了三角形。如果感兴趣,请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”

DFS c++版本的伪代码在二楼的答案:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}