在唐纳德·B·约翰逊算法的帮助下，我无法理解伪代码（PART II）

在唐纳德·B·约翰逊算法的帮助下，我无法理解伪代码（PART II）

有用！在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;     } }        }    }