2016-12-22 8 views
1

私は次回のインタビューで練習をしていますが、私が見つけた練習問題はO(V + E)グラフはbiconnectedです。 This page from Princetonによれば、アーティキュレーション頂点がない場合はグラフがbiconnectedとなり、アーティキュレーション頂点は接続されたコンポーネントの数を増やす頂点になります(バイコネクテッドグラフには1つの接続コンポーネントがあるので)。グラフがバイコネクトであるかどうかをこのアルゴリズムがどのように伝えるのか分かりません

この問題の一般的な解決策の1つは、追加のトラッキングを使用してDFSを実行して、いずれの頂点もアーティキュレーション頂点であるかどうかを確認することです。 Thisページでは、頂点が

  • Vは、少なくとも2人の子供 OR
  • Vとルートノードである場合には関節の頂点があるVの祖先を

しかし達することができない子供を持っていることを言いますルートノードの条件はわかりません。 enter image description here

すべてのノードをルートとして選択すると、ALLには2つ以上の子があるため、アーティキュレーションの頂点になり、グラフがバイコネクトされなくなります。これは接続されたコンポーネントを見つけるための一般的なアルゴリズムなので、私は何か誤解していると仮定します。グラフがバイコネクトされているかどうかを調べるには、ルートノードを実際に調べる必要がありますか?

答えて

1

あなたはあなたができるすべてを模索終わっまであなたが1--4リンクを探索することができないので、DFSツリーは常に

1 4 
| | 
2---3 

のように見えることを意味し、深さ優先探索を行うことになっています2に到達し、1を経由せずに、1--4を追加しません。これは、ツリーのエッジを含むサイクルになるためです。このツリーのノードには2つの子ノードがありません(1がルートです)。

+0

私は、ノードが最初にルートノード経由で訪問された場合、そのノードは子ノードですか? – CAJ

+0

@CAJ親ノードを介して、はい。 –

関連する問題