이분 그래프 (Bipartite Graph)
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.
•
즉, 그래프의 모든 정점이 두 그룹으로 나눠지고, 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 (< = > 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프 라고 한다.
이분 그래프의 특징
•
이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.
•
이분 그래프는 BFS를 할 때, 같은 레벨의 정점끼리는 무조건 같은 색으로 칠해진다.
•
연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.
•
모든 정점을 방문하며 간선을 검사하기 때문에, 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.
이분 그래프인지 확인하는 방법
이분 그래프인지 확인하는 방법은 너비우선탐색(BFS), 깊이우선탐색(DFS)을 이용하면 된다.
•
서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.
1.
BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.
2.
다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.
3.
탐색을 진행할 때, 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
•
BFS의 경우, 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면, 무조건 이분 그래프가 아니다.
4.
모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.
•
이때 주의할 점은 연결 그래프와 비연결 그래프 둘 다 고려해야한다는 점이다.
◦
그래프가 비연결 그래프인 경우, 모든 정점에 대해서 확인하는 작업이 필요하다.
예제) 백준 1707번 이분 그래프
•
인접 리스트 vector로 만들었다.
1.
DFS
•
빠짐없이 방문하기 위해서 1부터 N까지 다 돌려준다. 대신 방문 기록 있는 것들만 DFS 돌려주었다.
•
처음 방문하는 점이면 방문 기록에 RED를 넣어준다.
•
연결된 점 탐색하러 가는데 연결된 점도 방문한 적이 없으면, 일단 조건을 걸어준다. 탐색 시작한 노드가 RED 라면 연결된 점에는 BLUE를, BLUE 라면 RED를 넣어준다.
•
그리고 요소별로 방문하고 이것을 반복한다(재귀).
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define RED 2
#define BLUE 3
vector<int> graph[20001];
int visited[20001];
int V, E;
void dfs(int start) {
if (visited[start] == 0) visited[start] = RED;
for (int i = 0; i < graph[start].size(); i++) {
int index = graph[start][i];
if (visited[index] == 0) {
if (visited[start] == RED) visited[index] = BLUE;
else if (visited[start] == BLUE) visited[index] = RED;
dfs(index);
}
}
}
int check() {
for (int i = 1; i <= V; i++) {
for (int j = 0; j < graph[i].size(); j++) {
int index = graph[i][j];
if (visited[i] == visited[index]) return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, u, v;
cin >> T;
while (T--) {
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= V; i++) {
if (visited[i] == 0) dfs(i);
}
if (check() == 0) cout << "NO\n";
else cout << "YES\n";
memset(visited, 0, sizeof(visited));
memset(graph, 0, sizeof(graph));
}
}
C++
복사
2.
BFS
•
큐를 만들어주고 시작점을 큐에 먼저 push 한다.
•
큐의 맨 앞의 값을 복사해주고 큐를 pop 한다.
•
큐의 맨 앞 값이 RED면 인접리스트에 연결된 노드들은 모두 BLUE로 넣어주고, BLUE면 RED를 넣어준다.
•
check() 함수로 이분 그래프 검사를 한다.
•
인접한 노드와 시작점 노드가 색이 같으면 이분 그래프가 아니고, 한번이라도 같은게 있으면 바로 return 한다.
•
그리고 중요한 점은, 이 문제는 테스트케이스가 있으므로 인접리스트와 방문 기록을 여러 번 써야 한다는 점이다. 그래서 cstring 라이브러리의 memset 함수를 사용하여 초기화 시켜준다.
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define RED 1
#define BLUE 2
vector<int> graph[20001];
int visited[20001];
int V, E, u, v;
void bfs(int start) {
queue<int> q;
q.push(start);
visited[start] = RED;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) {
q.push(y);
if (visited[x] == RED) visited[y] = BLUE;
else if (visited[x] == BLUE) visited[y] = RED;
}
}
}
}
bool check() {
for (int i = 1; i <= V; i++) {
for (int j = 0; j < graph[i].size(); j++) {
if (visited[i] == visited[graph[i][j]]) return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int K;
cin >> K;
while (K--) {
cin >> V >> E;
for (int i = 0; i < E; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for (int i = 1; i <= V; i++) {
if (visited[i] == 0) bfs(i);
}
if (check()) cout << "YES\n";
else cout << "NO\n";
memset(visited, 0, sizeof(visited));
memset(graph, 0, sizeof(graph));
}
}
C++
복사