グラフのエッジがループを形成しているかどうかを確認する方法についての情報を教えてもらえますか? どの情報も非常に役立ちます。よろしくお願いします。
5788 次
3 に答える
5
Kruskal アルゴリズム (質問にタグを付けたもの) は、頂点ごとに素集合で初期化された素集合データ構造を使用します。次に、エッジごとに、エッジの頂点が属する 2 つのセットがマージされます。2 つの頂点が既に同じセットにある場合は、ループが見つかりました。エッジが発生するたびにエッジを削除すると、スパニング ツリーが得られます。重みの昇順でエッジを並べ替えると、最小スパニング ツリーになります。
グラフにループが含まれているかどうかだけを知る必要がある場合は、DFS などのより単純なものを使用します。いずれかのノードに、既にアクセスされた隣接ノード (親以外) がある場合、サイクルが見つかりました。
于 2014-01-21T10:36:45.810 に答える
1
接続するエッジが同じクラスタの頂点間にないかどうかをチェックする高速な結合検索データ構造の使用です。
于 2014-01-21T14:01:23.523 に答える
1
グラフで完全な DFS を実行します。グラフ内の各ノードについて、2 つのブール変数「visited」と「completed」を維持します。'visited' は頂点が訪問されたかどうかを示し、'completed' はその特定のノードから始まる DFS が完了したかどうかを示します。DFS を実行しているときに、既にアクセス済みであるが、その DFS がまだ完了していないノードにヒットした場合、グラフにサイクルが存在します。
于 2014-01-21T10:49:41.110 に答える