有用！在Johnson算法的早期迭代中，我以为那是一个邻接矩阵。相反，它似乎表示一个邻接表。在该示例中，如下实现，顶点{a，b，c}被编号为{0，1，2}，从而产生以下电路。
A
附录：如本建议的编辑和有用的答案所述，算法指定
unblock()应删除具有_值_
w的元素，而不是具有 索引 的元素
w。
list.remove(Integer.valueOf(w));
样本输出：
0 1 00 1 2 00 2 00 2 1 01 0 11 0 2 11 2 0 11 2 12 0 1 22 0 22 1 0 22 1 2
默认情况下，程序以
s = 0;开头。
s:=leastvertexinV仍然可以实现优化。这里显示仅产生唯一循环的变体。
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Stack; public final class CircuitFinding { final Stack<Integer> stack = new Stack<Integer>(); final List<List<Integer>> a; final List<List<Integer>> b; final boolean[] blocked; final int n; int s; public static void main(String[] args) { List<List<Integer>> a = new ArrayList<List<Integer>>(); a.add(new ArrayList<Integer>(Arrays.asList(1, 2))); a.add(new ArrayList<Integer>(Arrays.asList(0, 2))); a.add(new ArrayList<Integer>(Arrays.asList(0, 1))); CircuitFinding cf = new CircuitFinding(a); cf.find(); } public CircuitFinding(List<List<Integer>> a) { this.a = a; n = a.size(); blocked = new boolean[n]; b = new ArrayList<List<Integer>>(); for (int i = 0; i < n; i++) { b.add(new ArrayList<Integer>()); } } private void unblock(int u) { blocked[u] = false; List<Integer> list = b.get(u); for (int w : list) { //delete w from B(u); list.remove(Integer.valueOf(w)); if (blocked[w]) { unblock(w); } } } private boolean circuit(int v) { boolean f = false; stack.push(v); blocked[v] = true; L1: for (int w : a.get(v)) { if (w == s) { //output circuit composed of stack followed by s; for (int i : stack) { System.out.print(i + " "); } System.out.println(s); f = true; } else if (!blocked[w]) { if (circuit(w)) { f = true; } } } L2: if (f) { unblock(v); } else { for (int w : a.get(v)) { //if (v∉B(w)) put v on B(w); if (!b.get(w).contains(v)) { b.get(w).add(v); } } } v = stack.pop(); return f; } public void find() { while (s < n) { if (a != null) { //s := least vertex in V; L3: circuit(s); s++; } else { s = n; } } } }
