[알고리즘] 이분 그래프(Bipartite Graph)

이분 그래프

---

이분 그래프

조건 : 두 개의 색으로만 구분, 인접한 정점이 같은 색을 가지면 안됨.

Concept

• 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.
• 위 사진과 같이 두 개의 그룹으로 나누어지며, 같은 그룹의 정점은 인접하지 않음.
• 간선(E)이 아예 없고, 정점(V)만 있는 경우도 이분 그래프에 속함.

---

Feature

• 주어진 그래프가 이분 그래프인지 확인하기 위해서는 BFS, DFS 탐색을 활용.
• 완전탐색의 일종으로 모든 정점을 방문하여 검사하기 때문에 O(V+E)의 시간복잡도를 가짐
• 인접 정점 간의 싸이클(Cycle)이 발생할 경우 홀수 싸이클의 경우 이분 그래프를 절대 만족 못함.

 

---

Implement

너비 우선 탐색(BFS)를 활용한 탐색

1. 인접리스트를 활용하여 양방향 그래프 입력.
2. 방문하지않은 모든 정점에 대해서 BFS 탐색
3. 시작 정점에 대해서 임의의 색(빨강:1)을 방문체크 배열에 입력
4. while문을 돌면서 인접한 정점들에 대해 방문하지 않은 정점이라면 반대 색(파랑:-1) 입력
5. 인접정점이며 방문했었던 정점에 대해서 현재 정점과 비교하여 색이 같은지 비교
6. 색이 같다면 이분 그래프의 특성 만족 못하므로 flag 수정 및 탐색 종료.

Source Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int V, E;
    static ArrayList<ArrayList<Integer>> list;
    static int[] v;
    static boolean flag = true;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); //정점 입력
        E = Integer.parseInt(st.nextToken()); //간선 입력
	
				//정점의 개수만큼 인접 리스트 초기화
        list = new ArrayList<>();
        for(int i=0; i<V; i++) list.add(new ArrayList<>());

				//양방향 그래프 입력
        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            list.get(x).add(y);
            list.get(y).add(x);
        }

        v = new int[V]; //방문체크 배열(int형으로! : 각 정점별로 색 구분을 위해)

				//
        for(int i=0; i<V; i++) {
            if(v[i] == 0) bfs(i);
            if(!flag) break;
        }

        System.out.println(flag?"이분 그래프!!":"이분 그래프 X");
    }

    private static void bfs(int x) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(x);
        int color = 1; //1은 빨강, -1은 파랑으로 구분
        v[x] = color; //시작정점 구분

        while(!q.isEmpty()) {
            int cur = q.poll();
            color = v[cur] * -1; //현재 정점의 반대 색

            for(int now : list.get(cur)) { //인접한 정점들에 대해서
                if(v[now] == 0) { //방문하지않은 정점에 대해
                    v[now] = color;
                    q.offer(now);
                    continue;
                }
                if(v[now] == v[cur])  { //이미 방문한 정점의 색이 현재정점의 색과 같다면 이분 그래프가 아님
                    flag = false;
                    return;
                }
            }
        }
    }
}

 

---

Reference

백준 온라인 저지 사이트(BOJ) 의 경우 [BOJ_1707 이분 그래프], [BOJ_12893 적의 적] 두 개의 문제가 대표적인 이분 그래프 탐색 문제! 위 BFS코드를 일부 수정하면 풀이 가능

 

DFS에 대한 풀이는 추후 업로드 예정!!