[자료구조] 이분 그래프(Bipartite Graph)란 ?

이분 그래프의 개념

이분 그래프(Bipartite Graph)는 정점을 두 개의 집합으로 나눌 수 있고, 같은 집합에 속한 정점끼리는 간선이 연결되지 않는 그래프입니다. 즉, 모든 간선이 한 집합의 정점에서 다른 집합의 정점으로만 연결됩니다

이분 그래프의 특징

- 이분 그래프인지 확인하는 방법은 BFS, DFS 탐색을 이용하면 된다.

- 이분 그래프는 BFS를 할 때 같은 레벨의 정점끼리는 모조건 같은 색으로 칠해진다.

- 사이클의 길이가 홀수이면 이분 그래프가 아니다. (예: 3개의 정점으로 이루어진 삼각형(사이클 길이 3)은 이분 그래프가 아니다)

- 연결 성분의 개수(Connected Component)를 구하는 방법과 유사하다.

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

실생활 예시

• 사람과 취미를 연결하는 그래프
• 구직자와 회사 매칭
• 학생과 과목 선택 관계 등

 

이분 그래프인지 확인하는 방법

- 이분 그래프인지 확인하는 방법은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용하면 된다.

       - 서로 인접한 정점이 같은 색이면 이분 그래프가 아니다.

1. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.

2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.

3. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.

4. BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.
- 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.(색칠 규칙을 위반하지 않고 모든 정점을 탐색했으면 → 이분 그래프 맞음)

-   이때 주의할 점은 연결 그래프와 비연결 그래프를 둘 다 고려 해야한다는 것이다.

 

-   그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요하다.

       이분 그래프 판별할 때 DFS/BFS는 하나의 연결된 조각만 탐색한다.
        그런데 그래프가 비연결이면 **모든 조각(컴포넌트)**을 하나씩 확인해봐야 한다.

• 그래프가 다음과 같이 3개 컴포넌트로 되어 있다면:
  • (0-1), (2-3), (4-5-6)
• 우리는 각각의 컴포넌트를 따로따로 DFS/BFS로 돌려야 한다.
• 한 군데라도 이분 그래프 조건 위반하면 전체도 이분 그래프이다.

백준 1707 이분 그래프 문제풀이 (with kotlin)

 

package com.chanhue.algorithm.백준.골드

import java.util.LinkedList
import java.util.Queue

fun main() {
    // 테스트 케이스 수 입력
    val k = readLine()!!.toInt()

    // 이분 그래프인지 판별하는 함수
    fun DFS(graph: Array<MutableList<Int>>): Boolean {
        // 각 정점의 색을 저장하는 배열 (0: 방문 안 함, 1: 빨강, -1: 파랑)
        val color = IntArray(graph.size + 1) { 0 }

        // 그래프는 여러 연결 요소로 이루어질 수 있으므로 전체 정점 반복
        for (start in 1 until graph.size) {
            // 방문하지 않은 정점이면 BFS 시작
            if (color[start] == 0) {
                val queue: Queue<Int> = LinkedList()
                queue.add(start)
                color[start] = 1 // 시작 정점을 빨강(1)으로 색칠

                while (queue.isNotEmpty()) {
                    val vertex = queue.poll()

                    // 인접 정점 순회
                    for (next in graph[vertex]) {
                        // 방문 안 한 경우, 현재 정점의 반대 색으로 칠하고 큐에 추가
                        if (color[next] == 0) {
                            color[next] = color[vertex] * -1
                            queue.add(next)
                        }
                        // 이미 색이 칠해졌는데, 현재 정점과 색이 같으면 이분 그래프 아님
                        else if (color[next] == color[vertex]) {
                            return true // 충돌 발생
                        }
                    }
                }
            }
        }
        return false // 충돌 없이 모든 정점 처리 완료 → 이분 그래프
    }

    // 각 테스트 케이스 반복
    repeat(k) {
        val (v, e) = readLine()!!.split(" ").map { it.toInt() }
        val graph = Array(v + 1) { mutableListOf<Int>() } // 1번부터 v번까지 사용

        // 간선 입력 받아서 무방향 그래프 구성
        repeat(e) {
            val (v1, v2) = readLine()!!.split(" ").map { it.toInt() }
            graph[v1].add(v2)
            graph[v2].add(v1)
        }

        // 이분 그래프 여부에 따라 결과 출력
        val isNotBipartite = DFS(graph)
        if (isNotBipartite) {
            println("NO")
        } else {
            println("YES")
        }
    }
}

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