小编典典

了解唐纳德·B·约翰逊算法中的伪代码

algorithm

有谁知道唐纳德·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;” 行。这是什么意思?

如果有人可以将1970年的伪代码转换为更现代的伪代码,这样我才能理解,那将是很好的

如果您有兴趣提供帮助,但找不到该文件,请给我发送电子邮件pitelk@hotmail.com,我将向您发送该文件。


阅读 425

收藏
2020-07-28

共1个答案

小编典典

伪代码让人联想到Algol,Pascal或Ada。

这是否意味着我必须实施另一种找到A k矩阵的算法?

甲ķ似乎是具有指定属性的输入值的阵列的列表。它可能与相应的邻接矩阵有关,但我不清楚。我猜是这样的:

int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;

什么logical f意思

这声明了一个表示a truefalse值的局部变量,类似于Java的boolean

logical procedure CIRCUIT (integer value v);

这将声明一个子程序CIRCUIT,该子程序具有一个v按值传递的单个整数参数。子程序返回或的logical结果,并将其分配为结果。在Java中,true``false``CIRCUIT := f``f

boolean circuit(int v) {
    boolean f;
    ...
    f = false;
    ...
    return f;
}

关键字beginend定界可能嵌套的块作用域,因此CIRCUIT嵌套在主块中,UNBLOCK并嵌套在中CIRCUIT:=是分配;¬not;是元素;是空的; !=;stackunstack建议pushpop

这只是一个开始,但我希望对您有所帮助。

附录:在反思,A并且B必须是同构的。

这是一个 非常字面的 轮廓。我对&的了解不足A,无法选择比数组更好的数据结构。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;
            }
        }
    }
}
2020-07-28