C++でDFS(深さ優先探索)を使ってグラフが2部グラフかどうかを判定する方法

連結グラフが与えられたとき、そのグラフが2部グラフ(bipartite graph)であるかどうかを判定することを考えます。2部グラフとは、頂点集合を2つのグループに分割でき、すべての辺が必ず異なるグループの頂点同士を結ぶようなグラフのことです。言い換えると、隣接する頂点同士が常に異なる色になるように、グラフ全体を2色で塗り分けられるグラフです。

例えば、次のような6頂点のグラフを考えてみましょう。

この場合、出力は True(1)となります。このグラフは偶数長の閉路を持ち、2色での塗り分けが可能だからです。

解き方のアプローチ

この問題は、DFS(深さ優先探索)を用いて頂点を順番に彩色していくことで解けます。具体的な手順は以下の通りです。

• insert_edge()関数を定義する。引数として隣接リスト配列 adj、頂点 u、v を受け取ります。
  • adj[u] の末尾に v を追加する
  • adj[v] の末尾に u を追加する(無向グラフなので両方向に登録)
• is_bipartite_graph()関数の中で、隣接リスト adj[v] に含まれる各頂点 u に対して次の処理を行います。
  • visited[u] が false の場合:
    • visited[u] := true として訪問済みにする
    • color[u] := color[v] の反転(隣接頂点には必ず別の色を割り当て)
    • 再帰呼び出し is_bipartite_graph(adj, u, visited, color) が false を返した場合は、false を返す
  • それ以外の場合で、color[u] と color[v] が同じ色なら、false を返す(2部グラフではないことが確定)
• すべての隣接頂点を矛盾なく処理できたら、true を返す

なぜこの方法で判定できるのか

グラフが2部グラフであるための必要十分条件は「奇数長の閉路を含まない」ことです。DFSで隣接頂点を交互に色分けしていき、すでに訪問済みの頂点と同じ色になってしまった場合、そこには奇数長の閉路が存在することになり、その時点で2部グラフではないと判定できます。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void insert_edge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}
bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
    for (int u : adj[v]) {
       if (visited[u] == false) {
          visited[u] = true;
          color[u] = !color[v];
          if (!is_bipartite_graph(adj, u, visited, color))
             return false;
       }
       else if (color[u] == color[v])
          return false;
   }
   return true;
}
int main() {
   int N = 6;
   vector<int> adj_list[N + 1];
   vector<bool> visited(N + 1);
   vector<int> color(N + 1);
   insert_edge(adj_list, 1, 2);
   insert_edge(adj_list, 2, 3);
   insert_edge(adj_list, 3, 4);
   insert_edge(adj_list, 4, 5);
   insert_edge(adj_list, 5, 6);
   insert_edge(adj_list, 6, 1);
   visited[1] = true;
   color[1] = 0;
   cout << (is_bipartite_graph(adj_list, 1, visited, color));
}

入力

insert_edge(adj_list, 1, 2);
insert_edge(adj_list, 2, 3);
insert_edge(adj_list, 3, 4);
insert_edge(adj_list, 4, 5);
insert_edge(adj_list, 5, 6);
insert_edge(adj_list, 6, 1);

出力

1

出力が 1(true) となったことから、このグラフは2部グラフであることが確認できます。計算量は頂点数を V、辺数を E とすると O(V + E) であり、非常に効率的な判定手法です。