07)이분 그래프 판별(Bipartite Graph Distinction)

▣Bipartite Graph Distinction(이분 그래프 판별)

: 이분그래프의 여부를 판별하는 알고리즘

-> 이분 그래프 정의:  그래프의 모든 정점을 2그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 한다.

: 다음 알고리즘은 위 그래프가 2분그래프인지를 확인하는 알고리즘이다.
 : 그림에서 볼 수 있는 것과 같이 하나의 간선에 연결된 정점은 다른 색을 가지고 있는 것을 볼 수가 있다.
 : 즉, BFS 혹은 DFS를 이용하여 탐색을 하며 이미 visit된 정점을 확인할 당시 자기와 같은 색을 갖고 있다면, 이분 그래프가 아님을 확인 할 수가 있다.

<알고리즘 진행순서>

-DFS기준-

: 이런식으로 DFS의 탐색순서를 따라가며, visit 처리를 색으로 구분하게 된다.
: 이미 visit된 정점을 확인할 경우, 자신과 같은 색인경우는 이분그래프가 실패함을 알 수 있다.

<소스코드>

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
enum color { RED, BLUE };
 
vector <int> RED_GROUP;
vector <int> BLUE_GROUP;
vector <int> map[20001];
 
int vertex[20001];
string res = "YES";
int v, e;
int cnt = 0;
 
void dfs(int v_, int color) {
    vertex[v_] = color;
    if (color == RED)
        RED_GROUP.push_back(v_);
    else if (color == BLUE)
        BLUE_GROUP.push_back(v_);
    cnt++;
    if (cnt == v)
        return;
 
    for (int i = 0; i < map[v_].size(); i++) {
        if (vertex[map[v_][i]] == -1)
            dfs(map[v_][i], (color + 1) % 2);
        if (vertex[map[v_][i]] == color) {
            res = "NO";
            return;
        }
    }
 
    return;
}
 
int main() {
    int t;
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        res = "YES";
        for (int j = 0; j < 20001; j++) {
            vertex[j] = -1;
            map[j].clear();
        }
        cin >> v >> e;
 
        for (int j = 0; j < e; j++) {
            int v_1, v_2;
            cin >> v_1 >> v_2;
 
            map[v_1].push_back(v_2);
            map[v_2].push_back(v_1);
        }
 
        for (int j = 1; j <= v; j++) {
            if (vertex[j] == -1)
                dfs(j, RED);
        }
        cout << "이분 그래프 여부 : ";
        cout << res << endl;
        if (!res.compare("YES")) {
            
            cout << "RED GROUP : ";
            for (int i = 0; i < RED_GROUP.size(); i++) {
                cout << RED_GROUP[i] << " ";
            }
            cout << "\nBLUE GROUP : ";
            for (int i = 0; i < BLUE_GROUP.size(); i++) {
                cout << BLUE_GROUP[i] << " ";
            }
            cout << endl;
        }
    }
 
 
    return 0;
}

<결과 화면>

<성능>

모든 정점을 방문 하며 간선을 검사하기 때문에 시간 복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다.