给定图邻接矩阵(例如 g[][]),图是有向的。需要找到所有图形循环的计数(如果存在)并打印它们。
我试图用 Java 编写这个算法,有时它可以正常工作。如果图有复杂的循环,算法会返回疯狂循环。请查看我的代码并帮助解决此问题
public static final int k = 6;
public static int g[][] = { { 0, 1, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 1, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 } };
public static Vector stack = new Vector();
public static void printStack() {
System.out.print("stack is: { ");
for (int i = 0; i < stack.size(); i++) {
System.out.print(stack.get(i) + " ");
}
System.out.println("};");
}
public static boolean checkCycle() {
boolean res = false;
for (int i = 0; i < stack.size() - 1; i++) {
if (stack.get(i).equals(stack.lastElement())) {
res = true;
break;
}
}
return res;
}
public static boolean go_to_line(int line) {
boolean res = false;
for (int i = 0; i < k; i++) {
if (g[line][i] == 1) {
stack.add(i);
if (checkCycle() == true) {
System.out.println("Cycle found!");
res = true;
} else {
res = go_to_line(i);
}
}
}
return res;
}
public static int cycles_count() {
int res = 0;
for (int i = 0; i < k; i++) {
if (g[i][i] == 1) {
System.out.println("Knot detected at item {" + i + "}!");
res++;
}
for (int j = i + 1; j < k; j++) {
if (g[j][i] == 1) {
stack.add(j);
stack.add(i);
if (go_to_line(i) == true) {
res++;
System.out.print("Final ");
printStack();
stack.removeAllElements();
}
}
}
}
return res;
}