Псевдокод напоминает Алгол, Паскаль или Аду.
Значит ли это, что мне нужно реализовать другой алгоритм, который находит матрицу A k ?
A k представляется списком массивов входных значений, имеющих указанные свойства. Это может быть связано с соответствующей матрицей смежности , но мне это не ясно. Я предполагаю что-то вроде этого:
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;
Что означает logical f?
Здесь объявляется локальная переменная, представляющая значение true или false, аналогичное Java boolean.
.
logical procedure CIRCUIT (integer value v);
Здесь объявляется подпрограмма с именем CIRCUIT, имеющая единственный целочисленный параметр v, который передается по значению. Подпрограмма возвращает logical результат true или false, а CIRCUIT := f присваивает f результат. На Java
boolean circuit(int v) {
boolean f;
...
f = false;
...
return f;
}
Ключевые слова begin и end разграничивают область видимости блока, которая может быть вложенной, поэтому CIRCUIT вкладывается в основной блок, а UNBLOCK вкладывается в CIRCUIT. := это присвоение; ¬ равно not; ∈ является элементом; ∅ пусто; ≠ равно !=; stack и unstack предлагают push и pop.
Это только начало, но я надеюсь, что это поможет.
Приложение: При отражении 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;
}
}
}
}