有谁知道唐纳德·B·约翰逊算法,该算法在有 向 图中枚举所有基本电路(循环)?
我有他在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(integervaluev);"表示电路过程返回逻辑变量?伪代码中也有“ CIRCUIT := f;” 行。这是什么意思?
"logical procedure CIRCUIT(integervaluev);"
CIRCUIT := f;
如果有人可以将1970年的伪代码转换为更现代的伪代码,这样我才能理解,那将是很好的
如果您有兴趣提供帮助,但找不到该文件,请给我发送电子邮件pitelk@hotmail.com,我将向您发送该文件。
伪代码让人联想到Algol,Pascal或Ada。
甲ķ似乎是具有指定属性的输入值的阵列的列表。它可能与相应的邻接矩阵有关,但我不清楚。我猜是这样的:
int[][] a = new int[k][n]; int[][] b = new int[k][n]; boolean[] blocked = new boolean[n]; int s;
什么logical f意思
logical f
这声明了一个表示a true或false值的局部变量,类似于Java的boolean。
true
false
boolean
logical procedure CIRCUIT (integer value v);
这将声明一个子程序CIRCUIT,该子程序具有一个v按值传递的单个整数参数。子程序返回或的logical结果,并将其分配为结果。在Java中,true``false``CIRCUIT := f``f
CIRCUIT
v
logical
true``false``CIRCUIT := f``f
boolean circuit(int v) { boolean f; ... f = false; ... return f; }
关键字begin和end定界可能嵌套的块作用域,因此CIRCUIT嵌套在主块中,UNBLOCK并嵌套在中CIRCUIT。:=是分配;¬是not;∈是元素;∅是空的; ≠是!=;stack并unstack建议push和pop。
begin
end
UNBLOCK
:=
¬
not
∈
∅
≠
!=
stack
unstack
push
pop
这只是一个开始,但我希望对您有所帮助。
附录:在反思,A并且B必须是同构的。
A
B
这是一个 非常字面的 轮廓。我对&的了解不足A,无法选择比数组更好的数据结构。B``V
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; } } } }