이분 그래프 (Bipartite Graph)

이분 그래프 (Bipartite Graph)

 

이분그래프는 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 뜻한다.

 

다시 말해, 그래프의 모든 정점이 두그룹으로 나뉘어져있고 같은 그룹끼리는 인접하지 않은 그래프이다.

 

이분그래프를 확인하는 방법은 BFS 나 DFS를 이용한다.

1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색을 칠한다.

2. 각 정점을 방문 중, 자신과 인접한 정점의 색이 자신과 같다면 그 그래프는 이분 그래프가 아니다. (발견과 동시에 BFS 종료)

3. 모든 정점을 방문하고 인접한 정점끼리 같은색이 없다면 이분그래프이다.   

 

특징)

모든 정점을 방문하기 때문에 시간 복잡도는 O (V+E) 이다. 

 

아래의 코드는 백준사이트의 이분그래프를 풀면서 BFS 방식으로 작성한 코드이다.

 

이분 그래프 문제 www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int TC;
int V , E;
int vist[20001];
vector <int> graph[20001];

void init(int V){
    for(int i =1 ;i <= V;i++){
        graph[i].clear();
        vist[i] = 0;
    }
}
bool BFS(int v){
    queue <int> q;
    vist[v] = 1;
    q.push(v);

    while (!q.empty()){
        int curV = q.front();
        int curC = vist[curV];
        q.pop();

        for(int idx = 0 ; idx < graph[curV].size(); idx++){
            int nv = graph[curV][idx];
            if(vist[nv] == vist[curV]) return false; //이분 그래프가 아님 
            if(vist[nv] != 0 && vist[nv] != curC ) continue; // 이미 방문

            if(curC == 1) vist[nv] = -1; // 인접한다면 다른 집합으로 분리
            else vist[nv] = 1;
            q.push(nv);
        }
    }
    return true;
}
int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> TC;

    for(int tc = 0; tc < TC ; tc++){
        cin >> V >> E;
        bool flag = true;
        for(int i = 0; i < E; i ++){
            int v1 , v2;
            cin >> v1 >> v2;
            graph[v1].push_back(v2); // 양방향 그래프로 만들어야함
            graph[v2].push_back(v1);
        }

        for(int v=1; v<=V; v++){
            if(vist[v] == 0){
                if (BFS(v) == false){ //이분그래프가 아닐경우 NO 출력
                    cout<< "NO\n";
                    flag = false;
                    break;
                }
            }
        }
        if(flag) cout<<"YES\n";
        init(V);
    }
    return 0;
}