3

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

2 回答 2

5

这个问题在一般情况下具有指数复杂性。问题是，如果每个顶点都连接到每个顶点，那么所有图循环的计数都超过2^n（任何节点子集形成几个循环）。

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

于 2010-02-15T06:29:08.607 回答
1

如果 C++ 是问题所在，那么请更改为另一种语言。据我所知，C++ 没有使处理图形问题更高效/更方便的特定功能。或者，您可能想寻找一个抽象低层次的框架，让您专注于高层次的问题。为此，您可能会考虑使用Boost Graph 库。

于 2010-02-15T05:15:35.900 回答