アルゴリズム - グラフ内のすべてのコネクタを検索

Question

定義：無向グラフでは、頂点vはコネクタです。xとwの間のすべてのパスがvを通過する少なくとも2つの他の頂点xとwがある場合、

グラフを格納するために隣接リンクリストを使用しています。

私の最初の考えは「おお、頂点は、頂点の唯一の隣人の場合はコネクタです」

これは動作しますが、頂点がその品質を持っていなくても、頂点がコネクタである場合があります。

私は頂点の隣のすべてのパスをチェックして、他のすべての頂点に到達できるかどうかを確認するソリューションを考え出しました。おそらくこれは非常に時間がかかると想像できるでしょう。

私はより早いアルゴリズムを思いついたが、できなかった。誰も私にこの問題を解決する方法についてのヒントを教えてもらえますか？

Answer 1

グラフが接続されているとします。コネクターの頂点を削除する場合、グラフを切断する必要があります。次に、dfsまたはbfsを線形時間で使用してグラフのコンポーネントの数をカウントします。コンポーネントの数が変更された場合、削除された頂点またはノードがコネクタであることを意味します。

このアルゴリズムは、各頂点に対して実行できます。このアルゴリズムの時間複雑度はO(n^2)です。