C++로 DFS를 활용해 그래프가 이분 그래프(Bipartite)인지 판별하는 방법

연결된 그래프가 주어졌을 때, 해당 그래프가 이분 그래프(Bipartite Graph)인지 확인하는 문제를 살펴보겠습니다. 이분 그래프란 그래프의 모든 정점을 두 가지 색으로 칠할 때, 인접한 정점끼리는 서로 다른 색을 갖도록 칠하는 것이 가능한 그래프를 의미합니다. 즉, 같은 색의 정점들이 하나의 집합을 이루도록 나눌 수 있는 그래프입니다.

문제 예시

예를 들어 다음과 같은 그래프가 입력으로 주어진다고 가정해 보겠습니다.

이 경우 출력 결과는 True(1)가 됩니다.

접근 방법: DFS 기반 2-색칠하기

이 문제는 깊이 우선 탐색(DFS)을 활용한 그래프 색칠 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 임의의 시작 정점에 한 가지 색을 지정합니다.
• DFS로 인접 정점을 방문할 때마다 현재 정점과 반대되는 색을 부여합니다.
• 이미 방문한 정점의 색이 현재 정점의 색과 동일하다면, 두 인접 정점이 같은 색을 공유하는 것이므로 이분 그래프가 아닙니다.

알고리즘 단계

• insert_edge() 함수를 정의합니다. 이 함수는 인접 리스트 배열 adj와 두 정점 u, v를 받아 무방향 간선을 추가합니다.
• adj[u]의 끝에 v를 삽입합니다.
• adj[v]의 끝에 u를 삽입합니다.
• is_bipartite_graph() 함수에서는 다음을 수행합니다.
  • 현재 정점 v의 모든 인접 정점 u에 대해:
    • u를 아직 방문하지 않았다면:
      • visited[u]를 true로 설정합니다.
      • color[u]를 color[v]의 반전 값으로 지정합니다.
      • 재귀 호출 결과가 false라면 false를 반환합니다.
    • 이미 방문했는데 color[u]가 color[v]와 같다면 false를 반환합니다.
  • 모든 검사를 통과하면 true를 반환합니다.

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

동작 원리 및 시간 복잡도

위 예제의 그래프는 6개의 정점이 순환 구조(짝수 길이 사이클)를 이루고 있습니다. 짝수 길이 사이클은 두 가지 색으로 번갈아 칠하는 것이 가능하므로 이분 그래프에 해당하며, 결과로 1(True)이 출력됩니다.

참고로, 그래프 이론에서 중요한 성질 중 하나는 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 사이클을 포함하지 않는 것이라는 점입니다. 따라서 DFS 탐색 중 인접한 두 정점이 같은 색을 갖게 되는 상황이 발생한다면, 그 그래프에는 홀수 사이클이 존재한다고 볼 수 있습니다.

이 알고리즘의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 개수, E는 간선의 개수를 의미하며, 각 정점과 간선을 최대 한 번씩만 방문하기 때문입니다. 공간 복잡도 역시 방문 배열과 색상 배열, 재귀 호출 스택을 고려하여 O(V)입니다.