在有向图中找到所有循环 [英] 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

推荐答案

我在搜索中找到了此页面，由于周期与强连接的组件并不相同，因此我一直进行搜索，最后，我找到了一种有效的算法，其中列出了所有有向图的（基本）循环。它来自唐纳德·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

A <可以在此处中找到约翰逊算法的em> 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屋！