訪問したすべてのノードにフラグを立てることを考えました。フラグが設定されているノードを見つけたとき、それはサイクルです。ただし、1 つのノードが複数の親と複数の子を持つことができるため、これは機能しません。サイクルを見つけるにはどうすればよいですか？
PS: サイクルを見つけるには DFS の方が適していることはわかっていますが、BFS で行う必要があります。
質問する
1650 次
2 に答える
0
上記の答えは正しいですが、BFS ではないか、少なくとも直感的な BFS ではないと思います。これは主に、各ノードの出力エッジを確認し、入力エッジのないノードに接続されているエッジを削除することに依存します。私の答えは、この問題に対するより直感的な BFS 実装かもしれません。
サイクルとは何かを考えてみましょう。
ノードは自分自身に到達するパスを見つけることができ、その後サイクルがあります。
では、なぜ DFS は検索サイクル タスクを解決できるのに、BFS は解決できないのでしょうか?
有向グラフでサイクルを見つけるには、まず DFS を考えます。DFS ツリーにバック エッジがある場合、グラフにサイクルが存在します。DFS ツリーを構築するときに、各ノードの開始カウンターと終了カウンターを記録して、ポインティング ノードが現在のノードの祖先であるかどうかを確認できます。バック エッジが検出されると (ポインティング ノードは終了していませんが、現在のノードの前に開始されます)、ノードがその祖先の 1 つに戻る方法を見つけることができることを意味します。BFS は隣人を完全に探索するために使用されますが、先祖を救うことはできません。したがって、グラフを通過するときに先祖を保存すれば、この問題で BFS を機能させることができるかもしれません。
BFS の間、各ノードが近隣 (または子) を探索するときに、蓄積された祖先情報を近隣に送信します。親から渡された祖先の 1 つが自分自身であることをノードが検出すると、グラフにサイクルが発生します。これは、このアルゴリズムのステップを示す図です。
ステップ 1、A は近隣の B、C、D、E を探索し、祖先情報 {A} を送信します。
ステップ 2、B は近隣の E を探索し、祖先情報 {A, B} をそれに送信します。
ステップ 3、C は近隣の D、F を探索し、祖先情報 {A、C} を送信します。
ステップ 4、D は近隣を検出しません。
ステップ 5、F は近隣の D、G を探索し、祖先情報 {A、C、F} をそれらに送信します。
ステップ 6、G は近隣の C を探索し、祖先情報 {A、C、F、G} をそれに送信します。その後、C は自分の祖先が自分自身であることを発見し、サイクルが発生します。
では、このアルゴリズムの実行時間はどうでしょうか? 従来の BFS の実行時間は Theta(V+E) ですが、このアルゴリズムでは、先祖情報の受け渡しと結合に合計 E ステップかかりますが、各ステップの情報の配列サイズは 1 より大きく、C*V より小さくなります。したがって、合計実行時間は O(EV)、オメガ(V+E) です。
于 2020-02-19T20:00:30.667 に答える