使用邻接矩阵在C++中找到有向图中所有环的算法

Question

给定图的邻接矩阵（例如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;
}

- Pavel Belov

---

我怀疑没有人会为你编写代码。你需要展示你尝试过的内容，以及至少描述一些你遇到的问题。 - Jerry Coffin

你有没有考虑过可能存在无限多的循环？ - user461595

Answer 1

这个问题在一般情况下是指数复杂度的。事实上，如果每个顶点都相互连接，则所有图形循环的计数大于2^n（任何节点子集都形成多个循环）。

因此，在一般情况下没有好的算法。 要找到一些循环，可以使用广度优先搜索。要找到所有循环，应使用暴力算法。

- Alexey Malistov

Answer 2

如果C++是问题，那就换一种语言。据我所知，C++没有特别的功能使其更有效/方便地处理图形问题。或者你可以寻找一个框架来抽象低级别，让你专注于高级别的问题。你可以考虑使用Boost Graph library来实现这个目的。

- call me Steve