이분 그래프(Bipartite Graph)란 그래프의 모든 정점을 두 가지 색으로 칠할 수 있으면서, 서로 인접한 정점끼리는 항상 다른 색을 갖도록 만들 수 있는 그래프를 의미합니다. 다시 말해, 같은 색으로 칠해진 정점들은 하나의 집합을 이루며, 간선은 항상 서로 다른 집합 사이에만 존재합니다.
이 글에서는 BFS(너비 우선 탐색)를 활용하여 주어진 그래프가 이분 그래프인지 여부를 판별하는 C++ 프로그램을 살펴보겠습니다.
알고리즘 동작 원리
BFS 기반 이분 그래프 판별은 그래프 색칠 문제(k=2인 경우)를 응용한 방식입니다. 핵심 단계는 다음과 같습니다.
시작
함수 Bipartite():
1) 시작 정점(source vertex)에 한 가지 색을 지정한다.
2) 시작 정점의 모든 인접 정점에는 반대 색을 지정한다.
3) 그 인접 정점들의 이웃에는 다시 첫 번째 색을 지정한다.
4) 위 과정을 반복하며 k=2인 색칠 문제의 제약 조건을 만족하도록 모든 정점에 색을 지정한다.
5) 색을 지정하는 도중 현재 정점과 같은 색으로 이미 칠해진 인접 정점을 발견하면,
두 가지 색으로 그래프를 완성할 수 없으므로 해당 그래프는 이분 그래프가 아니다.
끝즉, BFS로 그래프를 순회하면서 레벨(level)이 홀수인 정점과 짝수인 정점을 서로 다른 색으로 칠해 나가다가, 인접한 두 정점이 같은 색을 갖게 되는 순간 이분 그래프가 아니라고 판단하는 것입니다.
C++ 구현 예제
#include <iostream>
#include <queue>
#define V 5
using namespace std;
bool Bipartite(int G[][V], int s) {
int colorA[V];
for (int i = 0; i < V; ++i)
colorA[i] = -1; // 모든 정점을 미색칠 상태(-1)로 초기화
colorA[s] = 1; // 시작 정점에 색 지정
queue<int> q; // BFS 순회를 위한 큐 생성 후 시작 정점 삽입
q.push(s);
while (!q.empty()) {
int w = q.front(); // 큐에서 정점 하나를 꺼냄(dequeue)
q.pop();
for (int v = 0; v < V; ++v) { // 아직 색칠되지 않은 모든 인접 정점 탐색
if (G[w][v] && colorA[v] == -1) {
// w에서 v로의 간선이 존재하고 v가 아직 색칠되지 않은 경우
colorA[v] = 1 - colorA[w]; // w와 반대되는 색을 v에 지정
q.push(v);
} else if (G[w][v] && colorA[v] == colorA[w]) {
// w에서 v로의 간선이 존재하는데 v가 w와 같은 색으로 칠해진 경우
return false; // 이분 그래프가 아님
}
}
}
return true; // 모든 인접 정점을 교차 색으로 칠하는 데 성공
}
int main() {
int G[][V] = {{ 0, 1, 0, 0},
{ 1, 0, 0, 0},
{ 0, 0, 0, 1},
{ 1, 0, 1, 0}};
if (Bipartite(G, 0))
cout << "The Graph is Bipartite" << endl;
else
cout << "The Graph is Not Bipartite" << endl;
return 0;
}실행 결과
The Graph is Bipartite
참고 사항
위 구현은 인접 행렬(adjacency matrix)을 사용하기 때문에 시간 복잡도는 O(V²)입니다. 만약 인접 리스트(adjacency list)를 사용하면 O(V + E)로 최적화할 수 있습니다.
또한 그래프가 연결 그래프가 아니라면, 모든 연결 요소(connected component)에 대해 각각 BFS를 수행해야 정확한 판별이 가능합니다. 특정 시작 정점에서 도달하지 못하는 정점이 남아 있으면 해당 정점을 새로운 시작점으로 하여 검사를 반복하면 됩니다.