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

Question

我无法理解唐纳德约翰逊发表的关于在图表中查找周期(电路)的论文的某些部分.

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

Ak:=由{s,s + 1,...... n}引起的G子图中具有最小顶点的强分量K的邻接结构;

为了让事情变得更糟,有些线路是"为了我在Vk做"而没有声明Vk是什么......

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

2)由节点列表引起的子图是包含所有这些节点以及连接这些节点的所有边的图.在文中,数学定义是"F是由W引起的G的子图,如果W是V的子集,并且F =(W,{u,y)| u,W在W中,而y(y,y)在E中)})其中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怎么办？

伪代码是我之前在Donald B. Johnson算法中理解伪代码的问题

这篇论文可以在唐纳德·约翰逊的算法中理解伪代码中找到

先感谢您

Answer 1

有用!在约翰逊算法的早期迭代中,我认为这是一个邻接矩阵.相反,它似乎代表邻接列表.在下面实现的该示例中,顶点{a,b,c}被编号为{0,1,2},产生以下电路.A

附录:如此提议的编辑和有用的答案中所述,算法指定unblock()应删除具有值 w的元素,而不是具有索引 的元素w.

list.remove(Integer.valueOf(w));

样本输出:

0 1 0
0 1 2 0
0 2 0
0 2 1 0
1 0 1
1 0 2 1
1 2 0 1
1 2 1
2 0 1 2
2 0 2
2 1 0 2
2 1 2

默认情况下,程序以s = 0; s := least vertex in V作为优化实施仍然存在.此处显示了仅产生唯一周期的变体.

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;
            }
        }
    }
}