algorithm - BFSによる無向グラフでアーティキュレーション頂点を見つける

Question

「グラフの幅優先探索を実行し、グラフのアーティキュレーションポイントを一覧表示する」のように聞こえる、無向グラフで問題が発生します。DFSを使用してアーティキュレーション頂点を見つけるアルゴリズムのみを見つけました。BFSでそれらの頂点を見つける方法はありますか？ありがとうございました。

更新：各ノードを削除してから、残りのグラフでBFSを実行するのはどうですか？すべてのノードをカバーしている場合、削除されたノードはアーティキュレーションポイントではありませんでした。非効率的だとは思いますが、大丈夫だと思います。

Answer 1

たくさんの余分な仕事をしなければなりません。

その理由は、ポイントがアーティキュレーションポイントであるかどうかを判断するには、その子、その子の子などを調べて、どのポイントがルート頂点に何らかの方法で接続されているかを確認する必要があるためです。深さ優先探索は自動的にそれを行います。幅優先探索はそうではありません。

シミュレートすることもできますが、幅優先探索を実行してから、深さ優先探索の中間状態をすべて記憶する必要があります。これは、実際の利益がないために多くのオーバーヘッドになります。