이분 그래프(Bipartite Graph)는 그래프의 모든 정점을 두 가지 색으로 칠할 수 있어서, 어느 정점도 인접한 정점과 같은 색을 갖지 않는 그래프를 의미합니다. 다시 말해, 정점들을 두 개의 집합으로 나누었을 때 모든 간선이 서로 다른 집합에 속한 정점들을 연결하는 구조입니다. 이 글에서는 DFS(깊이 우선 탐색)를 이용해 주어진 그래프가 이분 그래프인지 판별하는 C++ 프로그램을 살펴보겠습니다.
이분 그래프 판별 원리
DFS로 그래프를 순회하면서 시작 정점을 한 가지 색으로 칠하고, 인접한 정점에는 항상 반대 색을 칠합니다. 순회 도중 이미 색이 칠해져 있는 인접 정점의 색이 현재 정점과 같다면, 두 가지 색으로 그래프 전체를 칠하는 것이 불가능하므로 해당 그래프는 이분 그래프가 아닙니다. 참고로 그래프가 이분 그래프일 필요충분조건은 홀수 길이의 사이클(odd cycle)을 포함하지 않는 것입니다.
알고리즘
- 각 노드의 색(0 또는 1)을 저장하는 color[] 배열을 준비합니다. 두 값은 서로 반대되는 색을 나타냅니다.
- 임의의 노드에서 DFS 함수를 호출합니다.
- 노드 w를 아직 방문하지 않았다면, color[v]의 반대 값(!color[v])을 color[w]에 저장하고, w에 연결된 노드들을 방문하기 위해 DFS를 재귀적으로 호출합니다.
- 탐색 과정에서 인접한 두 정점 u, v가 같은 색으로 칠해져 있다면(color[u] == color[v]) 그래프는 이분 그래프가 아닙니다.
- 위 규칙을 반영하도록 DFS 함수를 수정합니다.
C++ 구현 예제
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
void addEd(vector<int> adj[], int w, int v) { // 그래프에 간선 추가
adj[w].push_back(v); // w의 리스트에 v 추가
adj[v].push_back(w); // v의 리스트에 w 추가
}
bool Bipartite(vector<int> adj[], int v,
vector<bool>& visited, vector<int>& color) {
for (int w : adj[v]) {
// 정점 w를 아직 탐색하지 않은 경우
if (visited[w] == false) {
// 현재 정점을 방문 처리
visited[w] = true;
color[w] = !color[v]; // 부모 정점과 반대되는 색 지정
if (!Bipartite(adj, w, visited, color))
return false;
}
// 인접한 두 정점이 같은 색이라면 이분 그래프가 아님
else if (color[w] == color[v])
return false;
}
return true;
}
int main() {
int M = 6;
vector<int> adj[M + 1];
// 노드의 방문 여부를 확인하기 위한 배열
vector<bool> visited(M + 1);
vector<int> color(M + 1); // 그래프의 정점을 두 가지 색으로 칠함
addEd(adj, 3, 2);
addEd(adj, 1, 4);
addEd(adj, 2, 1);
addEd(adj, 5, 3);
addEd(adj, 6, 2);
addEd(adj, 3, 1);
visited[1] = true;
color[1] = 0;
if (Bipartite(adj, 1, visited, color)) {
cout << "그래프는 이분 그래프입니다";
} else {
cout << "그래프는 이분 그래프가 아닙니다";
}
return 0;
}
실행 결과
그래프는 이분 그래프가 아닙니다
결과 해석
예제 그래프에는 정점 1 → 2 → 3 → 1로 이어지는 길이 3의 홀수 사이클이 존재합니다. 홀수 사이클을 포함하는 그래프는 두 가지 색만으로 모든 정점을 인접 정점끼리 다른 색이 되도록 칠할 수 없기 때문에, 이 그래프는 이분 그래프가 아닙니다.
시간 복잡도
이 알고리즘은 모든 정점과 간선을 각각 한 번씩만 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다.