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

Question

隣接行列Aを持つグラフGがあるとします。Gは二部構成です。 どのようにGの頂点を常に2つのグラフを形成する2つのセットに分割できますか？ ありがとう！

Answer 1

各要素を最初に0に設定して、頂点の数に等しいサイズの配列whichを宣言します。次に、グラフを深度優先で検索し、移動中の「レベル番号」を記録します。これは1から始まり、各エッジを横断して1と2の間で交互になります。到達したすべての頂点について、現在のレベルを対応するエントリwhichに割り当て、（以前は0だった場合は）その子を処理するために繰り返します。その後、whichのすべての要素は1または2になり、which[i]はどのセット頂点がiに属するかを示します。

直感的に言えば、DFS内の親から子への各トラバーサルがレベルを「下」にし、各トラバーサルバックがあなたを「上」に戻すと想像することができます。 2つのプロパティによって、偶数レベルのすべての頂点は奇数レベルの頂点にのみ接続でき、その逆もあります。したがって、ノードを「偶数」または「奇数」にラベル付けするだけで、2つのセットに分割するだけで十分です。

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