이분 그래프(Bipartite Graph)란?
이분 그래프는 그래프의 모든 정점을 두 가지 색상만으로 색칠할 수 있으면서, 인접한 정점끼리는 항상 서로 다른 색을 갖도록 구성된 그래프를 의미합니다. 즉, 정점들을 두 개의 집합으로 분할했을 때, 같은 집합에 속한 정점들은 동일한 색으로 칠해지며 서로 직접 연결되지 않습니다.
이번 글에서는 C++과 깊이 우선 탐색(DFS)을 활용하여 주어진 그래프가 이분 그래프인지 판별하는 프로그램을 살펴보겠습니다.
알고리즘
- 각 노드의 색상을 저장하기 위해
color[]배열을 사용합니다. 저장되는 값 0과 1은 서로 반대되는 두 가지 색을 나타냅니다. - 임의의 노드에서 DFS 함수를 호출합니다.
- 노드 w를 아직 방문하지 않았다면,
color[w]에 부모 노드와 반대되는 값인!color[v]를 할당한 뒤, w에 연결된 노드들을 계속 탐색하기 위해 DFS를 재귀적으로 호출합니다. - 탐색 도중 인접한 두 정점의 색상이 서로 같다면(
color[w] == color[v]) 해당 그래프는 이분 그래프가 아니므로 false를 반환합니다. - 충돌 없이 모든 정점을 순회했다면 true를 반환하며, 이는 그래프가 이분 그래프임을 의미합니다.
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 << "Graph is Bipartite";
} else {
cout << "Graph is not Bipartite";
}
return 0;
}
실행 결과
Graph is not Bipartite
결과 분석
예제 그래프에서 정점 1, 2, 3은 서로 연결되어 길이가 3인 홀수 사이클(삼각형)을 형성합니다. 일반적으로 홀수 사이클을 포함하는 그래프는 두 가지 색만으로 색칠할 수 없기 때문에 이분 그래프가 될 수 없습니다. 따라서 프로그램은 'Graph is not Bipartite'를 출력합니다.