그래프 이론 - 이분 그래프

🔘이분 그래프란 ?

 

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프

그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프

 

➿이분 그래프 특징

• 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.
• 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 무조건 같은 색으로 칠해진다.
• 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.
• 모든 정점을 방문하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.

 

☑️이분 그래프 판별 알고리즘

• 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.
• BFS, DFS 로 탐색하면서 정점 방문 할 때마다 두가지 색 중 하나를 칠한다.
• 다음 정점 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.
• 탐색 진행 할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
• BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.
• 모든 정점 다 방문했는데 위와 같은 경우 없다면 이분 그래프다
• 연결 그래프와 비연결 그래프 둘 다 고려해야 한다.
• 그래프가 비연결 그래프인경우 모든 정점에 대해 확인하는 작업이 필요하다.

c++ 코드 

//
//  1707_bgd.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/25.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

enum color { RED, BLUE };
 
vector<int> RED_GROUP;
vector<int> BLUE_GROUP;
string res = "";
int visit[20001];
vector<int> map[20001];
int cnt = 0;
int v, e;

void dfs(int vertex, int color){
    visit[vertex] = color;
    
    if(color == RED){
        RED_GROUP.push_back(vertex);
    }else if(color == BLUE){
        BLUE_GROUP.push_back(vertex);
    }
    cnt++;
    //cout << "m : " << map[vertex].size() << " " << endl;
    
    if(cnt == v) return; // vertex 다 돌면 종료
    
    for(int i = 0; i < (int)map[vertex].size(); i++){
        //cout << map[vertex][i]  << " " << endl;
        if(visit[map[vertex][i]] == -1){
            dfs(map[vertex][i], (color + 1) % 2);
        }
        if(visit[map[vertex][i]] == color){
            res = "NO";
            return;
        }
    }
    
}

int main(){
    cin >> v >> e; // vertex, edge
    memset(visit, -1, sizeof(visit));
    
    //fill(map.begin(), map.begin() + 20001, -1);
    res = "YES";
    for(int i = 0; i < e; i++){
        int v1, v2;
        cin >> v1 >> v2;
        map[v1].push_back(v2);
        map[v2].push_back(v1);
    }
    
    for(int j = 1; j <= v; j++){
        if(visit[j] == -1){ // 방문 하지 x으므로
            dfs(j, RED);
        }
    }
    
    cout << "이분 그래프 여부 "  << res << endl;
    
    if (!res.compare("YES")) {
       cout << "RED GROUP : ";
       for (int i = 0; i < (int)RED_GROUP.size(); i++) {
           cout << RED_GROUP[i] << " ";
       }
       cout << "\nBLUE GROUP : ";
       for (int i = 0; i < (int)BLUE_GROUP.size(); i++) {
           cout << BLUE_GROUP[i] << " ";
       }
       cout << endl;
    }
    
    return 0;
}