有谁知道 Donald B. Johnson's algorithm , 它枚举了有向图中的所有基本电路(循环)?
我有他在 1975 年发表的论文,但我看不懂伪代码。
我的目标是用 Java 实现这个算法。
我有一些问题,例如,它所指的矩阵 Ak 是什么。在伪代码中,它提到了
Ak:=adjacency structure of strong component K with least
vertex in subgraph of G induced by {s,s+1,....n};
这是否意味着我必须实现另一种算法来找到 Ak 矩阵?
另外一个问题是下面的是什么意思?
begin logical f;
"logical procedure CIRCUIT (integer value v);"
这行是否也意味着电路过程返回一个逻辑变量?在伪代码中还有一行“CIRCUIT := f;
”。这是什么意思?
如果有人能将这个 1970 年代的伪代码翻译成更现代的伪代码类型,以便我能够理解,那就太好了
如果您有兴趣提供帮助但找不到论文,请发送电子邮件至 pitelk@hotmail.com 我会将论文发送给您。
最佳答案
伪代码让人想起 Algol、Pascal 或 Ada。
Does that mean I have to implement another algorithm that finds the Ak matrix?
Ak 似乎是具有指定属性的输入值数组列表。可能与对应的adjacency matrix有关,但我不清楚。我猜是这样的:
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;
What does
logical f
mean?
这声明了一个表示true
或false
值的局部变量,类似于 Java 的 boolean
。
logical procedure CIRCUIT (integer value v);
这声明了一个名为 CIRCUIT
的子程序,它有一个按值传递的整数参数 v
。子程序返回 true
或 false
的 logical
结果,并且 CIRCUIT := f
分配 f
作为结果。在 Java 中,
boolean circuit(int v) {
boolean f;
...
f = false;
...
return f;
}
关键字begin
和end
界定了一个可以嵌套的 block 作用域,所以CIRCUIT
嵌套在主 block 中, UNBLOCK
嵌套在 CIRCUIT
中。 :=
是赋值; ¬
是不是
; ∈
为元素; ∅
为空; ≠
是!=
; stack
和unstack
建议使用push
和pop
。
这只是一个开始,但我希望它能有所帮助。
附录:根据反射,A
和 B
必须是同构的。
这是一个非常直白的大纲。我对 A
、B
和 V
了解不够,无法选择比数组更好的数据结构。
import java.util.Stack;
public final class CircuitFinding {
static int k, n;
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int[] v = new int[k];
int s = 1;
Stack<Integer> stack = new Stack<Integer>();
private void unblock(int u) {
blocked[u] = false;
for (int w : b[u]) {
//delete w from B(u)
if (blocked[w]) {
unblock(w);
}
}
}
private boolean circuit(int v) {
boolean f = false;
stack.push(v);
blocked[v] = true;
L1:
for (int w : a[v]) {
if (w == s) {
//output circuit composed of stack followed by s;
f = true;
} else if (!blocked[w]) {
if (circuit(w)) {
f = true;
}
}
}
L2:
if (f) {
unblock(v);
} else {
for (int w : a[v]) {
//if (v∉B(w)) put v on B(w);
}
}
v = stack.pop();
return f;
}
public void main() {
while (s < n) {
//A:= adjacency structure of strong component K with least
//vertex in subgraph of G induced by {s, s+ 1, n};
if (a[k] != null) {
//s := least vertex in V;
for (int i : v) {
blocked[i] = false;
b[i] = null;
}
L3:
circuit(s);
s++;
} else {
s = n;
}
}
}
}
关于java - 理解 Donald B. Johnson 算法中的伪代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2908575/