6

有谁知道Donald B. Johnson 的算法,它列举了有图中的所有基本电路(循环)?

我有他在 1975 年发表的论文,但我看不懂伪代码。

我的目标是在 Java 中实现这个算法。

我有一些问题,例如,它所指的矩阵 A k是什么。在伪代码中,它提到

Ak:=adjacency structure of strong component K with least 
    vertex in subgraph of G induced by {s,s+1,....n};

这是否意味着我必须实现另一种找到 A k矩阵的算法?

另一个问题是下面的意思是什么?

begin logical f; 

该行是否还"logical procedure CIRCUIT (integer value v);"意味着电路程序返回一个逻辑变量?在伪代码中也有一行“ CIRCUIT := f;”。这是什么意思?

如果有人能将这个 1970 年代的伪代码翻译成更现代的伪代码类型,那就太好了,这样我就可以理解了

如果您有兴趣提供帮助但找不到论文,请发送电子邮件至pitelk@hotmail.com 给我,我会将论文发给您。

4

2 回答 2

7
于 2010-05-26T05:09:14.643 回答
1

You can find a Java implementation of this algorithm on github: https://github.com/1123/johnson. It uses the Jung2 java graph library.

于 2013-02-13T20:47:27.260 回答