algorithm - グラフが2部グラフであるかどうかを確認するプログラムを作成する

Question

グラフが2部グラフであるかどうかをチェックするプログラムを作成する必要があります。

グラフ彩色と2部グラフに関するウィキペディアの記事を読みました。これらの2つの記事は、BFS検索のような二者択一をテストする方法を提案していますが、これらの方法を実装するプログラムを作成することはできません。

Answer 1

なぜできないのですか？あなたの質問は、特定の言語についても言及していないため、誰かがあなたのためにプログラムを書くことさえ難しくしています...

アイデアは、 FIFOキューにランダム ノードを配置することから始めることです (こちらも)。青色に着色します。次に、ノードがまだキューに残っている間、これを繰り返します: 要素をデキューします。抽出された要素とは異なる色でその隣接要素に色を付け、各隣接要素を FIFO キューに挿入 (エンキュー) します。たとえば、赤色の要素 (ノード) をデキュー (抽出) する場合は、その隣接要素を青色にします。青色のノードを抽出する場合は、その隣接ノードを赤色にします。色の競合がない場合、グラフは 2 部になります。2 つの異なる色でノードを着色することになった場合、それは 2 部構成ではありません。

@Moronが言ったように、私が説明したことは、接続されたグラフでのみ機能します。ただし、各連結要素に同じアルゴリズムを適用して、任意のグラフで機能させることができます。