3

有機的に構築されたグラフですべてのサイクルを見つけたい。簡単に言えば、2 つの分岐またはパスが共通の頂点で終了すると、サイクルが発生します。
1->2->3->4
1->5->4のようなもの
は、1->2->3->4->5->1 のサイクルを形成します。

グラフの性質上、バックエッジがないため、DFS や同様のアルゴリズムを使用できません。与えられた頂点座標と無向グラフのすべてのサイクル ベースを識別するアルゴリズムを使用して、グラフ内のすべてのサイクル ベースを検索して正しい方向に進むことがわかりましたが、2 つのスレッドで効率的なアルゴリズムが提示されませんでした。

疑似コードまたは実装された形式の最適化されたソリューションはありますか、それとも提示されたソリューションのいずれかに傾いて自分で最適化する必要がありますか? 後者の場合、この目的のために提供されたどのコード サンプルを使用すればよいでしょうか?

返信をお待ちしております。

4

2 に答える 2

0

DFSがあなたに合っていると思います。

すでに探索された頂点に遭遇するまで、グラフを探索します

これは擬似コードです:

function DFSFindCycle(Start, Goal)
push(Stack,Start)
while Stack is not empty
    var Node := Pop(Stack)
    Color(Node, Grey)
    for Child in ExpandNotExploredEdges(Node)
        if Node.color != White
    return true 
        if Node.color = White
           push(Stack, Child)
           label edge e, Node:Child as explored
    Color(Node, Black)
retrun false

それが役に立てば幸い

于 2013-05-20T12:14:41.893 に答える