algorithm - 帮助 Donalds B. Johnson 的算法，我无法理解伪代码(第二部分)

Question

我无法理解 Donald Johnson 发表的关于在图中查找循环(​​Circuits)的论文的特定部分。

更具体地说，我无法理解以下伪代码行中提到的矩阵 Ak 是什么:

Ak:=最小的强分量K的邻接结构 由{s,s+1,....n}导出的G子图中的顶点；

让事情变得更糟的是，后面的几行是“for i in Vk do”而没有声明 Vk 是什么......

据我所知，我们有以下内容:1)一般来说，强组件是一个图的子图，其中对于这个子图的每个节点都有一个到子图的任何节点的路径(换句话说，你可以访问图的任何节点来自子图的任何其他节点的子图)

2) 由节点列表诱导的子图是 包含所有这些节点以及连接这些节点的所有边的图。 在论文中，数学定义是“如果 W 是 V 的子集且 F = (W,{u,y)|u,y in W and (u,y) in E)}，则 F 是由 W 诱导的子图其中u,y是边，E是图中所有边的集合，W是节点的集合。

3) 在代码实现中，节点由整数 1 ... n 命名。

4) 我怀疑 Vk 是强分量 K 的节点集。

现在开始这个问题。假设我们有一个图 G= (V,E)，其中 V = {1,2,3,4,5,6,7,8,9} 它可以分为 3 个强分量 SC1 = {1, 4,7,8} SC2= {2,3,9} SC3 = {5,6}(及其边)

谁能给我一个 s = 1、s = 2、s = 5 的例子，如果根据代码要成为 Vk 和 Ak 会怎么样？

伪代码在我之前的问题中 Understanding the pseudocode in the Donald B. Johnson's algorithm

论文可以在 Understanding the pseudocode in the Donald B. Johnson's algorithm

提前谢谢你

Answer 1

有效!在 earlier iteration的 Johnson algorithm , 我原以为 A 是 adjacency matrix .相反，它似乎代表一个 adjacency list .在下面实现的那个例子中，顶点 {a, b, c}编号为 {0, 1, 2}，产生以下电路。

附录:如本提案中所述 edit很有帮助answer , 该算法指定 unblock() 应该删除具有 value w 的元素，而不是具有 index 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

By default, the program starts with s = 0; implementing s := least vertex in V as an optimization remains. A variation that produces only unique cycles is shown here.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @see http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
 * @see https://stackoverflow.com/questions/2908575
 * @see https://stackoverflow.com/questions/2939877
 * @see http://en.wikipedia.org/wiki/Adjacency_matrix
 * @see http://en.wikipedia.org/wiki/Adjacency_list
 */
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();
    }

    /**
     * @param a adjacency structure of strong component K with
     * least vertex in subgraph of G induced by {s, s + 1, n};
     */
    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;
            }
        }
    }
}