查找有向图中的所有循环 [英] Finding all cycles in a directed graph

问题描述

如何在有向图中找到(迭代)从/到给定节点的所有循环?

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?

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

For example, I want something like this:

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

但不是:B->C->B

but not: B->C->B

推荐答案

我在搜索中找到了这个页面，由于循环与强连通分量不同，我一直在搜索，最后，我找到了一个有效的算法，列出了所有有向图的(基本)循环.它来自 Donald B. Johnson，该论文可以在以下链接中找到:

I found this page in my search and since cycles are not same as strongly connected components, I kept on searching and finally, I found an efficient algorithm which lists all (elementary) cycles of a directed graph. It is from Donald B. Johnson and the paper can be found in the following link:

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

可以在以下位置找到 Java 实现:

A java implementation can be found in:

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

约翰逊算法的Mathematica演示可以在这里找到，实现可以从右侧下载(下载作者代码").

A Mathematica demonstration of Johnson's algorithm can be found here, implementation can be downloaded from the right ("Download author code").

注意:其实这个问题有很多算法.本文列出了其中一些:

Note: Actually, there are many algorithms for this problem. Some of them are listed in this article:

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

根据文章，约翰逊的算法是最快的.

According to the article, Johnson's algorithm is the fastest one.

这篇关于查找有向图中的所有循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！