graph - 二部グラフの分割隣接行列

Question

隣接行列 A を持つグラフ G があるとします。G が二部であることはわかっています。G の頂点を常に 2 部グラフを形成する 2 つのセットに分割するにはどうすればよいですか? ありがとう！

Answer 1

which頂点の数に等しいサイズの配列を宣言し、最初は各要素を 0 に設定します。次に、グラフに対して深さ優先検索を実行し、進行中の「レベル番号」を記録します。これは 1 から始まり、エッジを通過するたびに 1 と 2 を交互に繰り返します。到達した頂点ごとに、現在のレベルを の対応するエントリに割り当て、which(以前に 0 だった場合) 再帰してその子を処理します。その後、 のすべての要素はwhich1 または 2 のいずれかになり、which[i]どの集合頂点がi属するかを示します。

直観的に、DFS 内の親から子への各トラバーサルはレベルを「下」に移動し、各トラバーサルは「上」に戻ることを想像できます。二部特性により、偶数レベルのすべての頂点は奇数レベルの頂点にのみ接続でき、その逆も同様であるため、ノードを「偶数」または「奇数」とラベル付けするだけで、ノードを 2 つのセットに分割できます。

グラフに複数のコンポーネントが含まれている場合は、もちろんコンポーネントごとに個別の DFS が必要になります。