私はグラフを初めて使用するので、グラフ内のアーティキュレーション ポイントを見つける方法を明確に説明できるアルゴリズムを取得していません。誰か説明してください。事前に感謝
2551 次
2 に答える
0
簡単なアルゴリズム:
各ノード N について、次のようにします。 1. それを取り除きます。 2. 接続されたコンポーネントの数を数えます。dfs または bfs による。それがまだ 1 つである場合は、ループを続行します。2 の場合は、関節点を見つけたことになります。ループをマークして続行します。
これは二次時間で実行されます。より良いアルゴリズムがあるかどうかはわかりません。
編集:このサイトでいくつかの Java ソース コードを見つけました: http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html
于 2013-04-09T21:01:50.880 に答える