少なくとも2つの方法があることを知っています。
1 つの方法は、非巡回ツリーにエッジを追加するたびに、必要な頂点をトラバースすることです。
欠点は、ツリーが大きくなるにつれて、トラバース手順に時間がかかることです。
もう 1 つの方法は、追加されたエッジが無限ループを作成するかどうかを受動的にチェックすることです。
質問する
112 次
2 に答える
2
トポロジーの並べ替えがこれに関係する場所がわからないので、ノード間のリンクを作成するだけの場合の答えを次に示します。
最初は、切断されたノードのセットがあるとします。リンクを追加すると、ノードがリンクされてツリーになります。以前は別々だった 2 つのツリーを追加するリンクを作成しても、サイクルは作成されません。すでに同じツリーにある 2 つのノード間にリンクを追加すると、サイクルが作成されます。したがって、リンクしようとしている 2 つのノードが既に同じツリーにあるかどうかを確認することで、サイクルを確認できます。
これは共用体検索であり、これを行う効率的な方法はhttp://en.wikipedia.org/wiki/Disjoint-set_data_structureで説明されています。
于 2012-11-17T05:29:21.207 に答える
0
トポロジカルソートを行うと無料でサイクル検出が得られるため、トポロジカルソートについての言及について混乱しました。これはhttp://en.wikipedia.org/wiki/Topological_sortなどの多くの場所で説明されています。また、 http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithmsからサイクル検出を取得します。
これについて考えると、有向グラフでオンラインのサイクル検出を行おうとしているのだろうか。Unix のユーザー コードによって生成されたデッドロックを検出するコードで、このコードを見たことがあると思います。これは反復的であり、プロセスが 1 つのイベントだけを待機できるという事実に依存していました。これはあなたの「必要な頂点をトラバースする」に相当すると思います。
トポロジーの並べ替え順序を維持することに依存するスキームがいくつかあるようです。次に、順序と一致するリンクを追加すると、サイクルが導入されていないことがわかります。問題は、順序と一致しないリンクを追加した場合、サイクルをチェックして順序を維持する必要があることです。このような 3 つのアルゴリズムについては、http://homepages.ecs.vuw.ac.nz/~djp/files/tr0703.pdfで説明されています。
于 2012-11-17T06:54:43.650 に答える