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++には、グラフの問題をより効率的/便利にする特定の機能はありません。または、低レベルを抽象化して高レベルの質問に集中できるフレームワークを探すこともできます。そのためにブースト グラフ ライブラリを検討することもできます。

于 2010-02-15T05:15:35.900 に答える