14

グラフを指定すると、グラフ内のすべての最小サイクルが返されるアルゴリズムを探しています。
私が何を望んでいるのかを明確にするために、このグラフから次のサイクルを正確に返すアルゴリズムが必要です:
(1,3,6,1)、(1,6,4,1)、(1,4,2,1) , (6,4,7,6), (2,4,7,2), (2,7,5,2)
ここに画像の説明を入力

私はたくさん検索してきましたが、この問題の名前すらわかりません。それはサイクルベースの問題ですか、それとも基本的なサイクルの問題ですか、それとも同じですか? MST または All-Pairs Shortest Paths を含むソリューションを見つけましたが、どれも理解できません。
ここで見つけたホートンのアルゴリズムを実装しようとしました:ホートンのアルゴリズムですが、実際にサイクルを見つけようとして 5 ページの 4 番目のステップで行き詰まりました。
Horton のアルゴリズムのステップ 4 で正確に何をする必要があるかを誰かが説明してくれるか、私の問題を解決する別のアルゴリズムを教えてくれますか?

4

2 に答える 2

2

この論文では、幾何学的ツールライブラリで使用されるアルゴリズムについて説明します (ic C++ で書かれていると思います)。これは基本的に、いくつかの代数を追加した修正された DFS アルゴリズムです。疑似コードは大きすぎてここに投稿できないので、リンクを次に示します。

http://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf

私は現在、JavaScriptの実装に取り​​組んでいます。興味のある方はこちらからご覧いただけます：

http://jsbin.com/igujuz/8/edit

于 2013-08-14T15:39:03.287 に答える
0

このアルゴリズムは、重み付けされていないグラフでのみ機能します。

例：

INPUT GRAPH: A, B, C, D, E

A: B, C, E
B: A, C
C: A, B, D
D: C, E
E: A, D

アルゴリズム：

初期化

[LIST] = { }

LIST[A] = { A }
LIST[B] = { B }
LIST[C] = { C }
LIST[D] = { D }
LIST[E] = { E }

DISTANCE = 0

SOLVED = FALSE

SOLUTION = { }

探す

WHILE NOT SOLVED DO

    DISTANCE = DISTANCE + 1

    FOR EVERY LIST[X] IN [LIST]
        TEMP = LIST[X]
        LIST[X] = { }
        FOR EVERY VERTEX IN TEMP
            LIST[X] += NEIGHBORS(VERTEX)
        END-FOR
    END-FOR

    FOR EVERY LIST[X] IN [LIST]
        FOR EVERY VERTEX IN LIST[X]
            IF VERTEX = X THEN
                SOLUTION = { X, DISTANCE }
                SOLVED = TRUE
            END-IF
        END-FOR
    END-FOR

END-WHILE
于 2013-05-28T06:02:24.787 に答える