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

• 인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다.
• 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다.
• 시간복잡도: O(V+E)

1. 이분 그래프 알고리즘

• BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다.
• 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다.

 

1. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2)
   • 이때 인접한 노드와는 서로 다른 색을 선택한다.
   • 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다.
   • 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다.
   • $color_{next}= color_{before}$ $\%$ $2 + 1$ 공식을 통해 서로 다른 색을 표현할 수 있다.
2. 탐색하면서 인접한 노드의 색이 자신과 동일하면 이분 그래프가 아님으로 False를 return 한다.
3. 모든 노드들을 방문해도 괜찮았다면 이분 그래프임으로 True를 return 한다.

2. 이분 그래프 함수

from collections import defaultdict
def sol():
    v,e = map(int,input().split())
    color = [0]*(v+1) # 칠해줄 색을 담을 곳
    g = defaultdict(list)
    # 양방향 그래프
    for _ in range(e):
        x,y = map(int,input().split())
        g[x].append(y)
        g[y].append(x)
    
    # 모든 노드 탐색
    for i in range(1,v+1):
        if color[i]: # 이미 지나온 노드면 넘어가기
            continue
        # 새로 접한 노드면 색을 칠해주고 인접한 노드들 탐색
        color[i] = 1

        if bfs(i,g,color) == False:
            # 인접한 노드 색이 같았으므로 이분 그래프가 아님
            return "NO"

    # 끝까지 이상이 없다면 이분 그래프
    return "YES"

2.1. 이분 그래프의 BFS 함수

from collections import deque
def bfs(x,g,color):
    q = deque([x])
    while q:
        now = q.popleft()
        next_color = color[now] % 2 + 1 # 다음 노드의 색
        
        for next in g[now]:
            # 아직 방문하지 않았다면(0)
            if not color[next]: 
                color[next] = next_color # 색칠하기
                q.append(next)

            # 만약 인접 노드가 현재 노드와 같은 색이라면 이분 그래프가 아님
            elif color[next] != next_color: 
                return False

    # 끝까지 이상 없으면 아직은 이분 그래프
    return True

2.2. 이분 그래프의 DFS 함수

def dfs(x,g,color):
    stack = [x]
    while stack:
        now = stack.pop()
        next_color = color[now] % 2 + 1
        
        for next in g[now]:
            if not color[next]: 
                color[next] = next_color
                stack.append(next)

            elif color[next] != next_color: 
                return False

    return True