[Data Structure] Bipartite Graph (이분 그래프) | 자바

백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단하게 

• 이분 그래프란 ?
• 이분그래프의 탐색방법
  • BFS
  • DFS

로 진행하려고 한다!

 

* 이분 그래프의 개념과 글에 나온 이미지는 아래 글을 참고하였습니다 *

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

---

1. 이분 그래프란 ?

이분 그래프는 그래프 형태의 자료구조로, 인접하는 노드를 다른 색으로 칠했을 때, 두 가지 색으로 나타낼 수 있는 그래프를 의미한다. 즉, 정점을 두 그룹으로 나누었을 때 같은 그룹의 정점들끼리는 간선으로 이어지지 않는 그래프이다.

 

위 예시를 보면 빨간색 점끼리는 선으로 이어지지 않음을 알 수 있다 ! 이런 그래프를 이분 그래프라고 한다.

 

 

이분 그래프 특징

• 같은 depth의 노드들은 같은 색을 가진다
• 모든 정점을 방문해야 하기 때문에 시간복잡도는 일반 그래프 탐색 알고리즘과 같다. (O(V + E))
• 비연결 그래프 (그냥 노드 한개만 있는 경우) 도 이분 그래프이다 🌟 

 

---

2. 이분 그래프 탐색 방법

이분 그래프인지 여부를 확인하는 방법은 그래프 탐색 알고리즘인 BFS, DFS가 있다.

현재 방문한 노드의 색을 A라고 두면, 해당 노드에 인접한 노드들을 B로 칠해주는 식으로 탐색해주면 된다. 만약 인접한 노드의 색이 현재 방문해있는 노드의 색과 동일하다면 이분 그래프가 아니라고 판단할 수 있다.

 

또, 비연결 그래프일 경우도 있기 때문에, 아래 코드처럼 반복문을 통해 모든 노드를 돌아야 한다!

// Red = 1, Blue = -1
for (int i = 1 ; i <= node ; i++) {
               
                if (!isBipart) // 이분 그래프 여부 확인
                    break;
               
                if (colors[i] == 0) { // 방문하지 않은 노드만 탐색
//                    dfs(i, RED);
                    bfs(i, RED);
                }
}

 

 

<DFS>

private static void dfs(int now, int color) {
        colors[now] = color; // 색 설정 

        for (int adjV : arrayLists.get(startV)) {
            if (colors[adjV] == color) { // 인접 노드 색 확인 -> 같으면 이분그래프 X
                isBipart = false;
                return;
            }

            if (colors[adjV] == 0) { // 방문 X인 노드 방문
                dfs(adjV, -color); // 다른 색 지정
            }
        }
}

 

<BFS>

private static void bfs(int now, int color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(now); 
        colors[now] = color; 

        while (!queue.isEmpty() && checkBipartite) {
            int v = queue.poll();

            for (int adjV : arrayLists.get(v)) { // 인접노드들 방문

                if (colors[adjV] == 0) { // 방문 X 노드들 방문
                    queue.offer(adjV);
                    colors[adjV] = colors[v] * -1;
                }
                
                else if (colors[v] != colors[adjV]) {
                    isBipart = false;
                    return;
                }
           }
      }
}