Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 그래프가 이분 그래프(Bipartite Graph)인지 판별하는 프로그램

무방향 그래프(undirected graph)가 주어졌을 때, 해당 그래프가 이분 그래프(bipartite graph)인지 확인하는 문제를 살펴보겠습니다.

이분 그래프란 그래프의 모든 정점을 두 집합 A와 B로 나눌 수 있어서, 그래프의 모든 간선 {u, v}에 대해 한쪽 끝점 u는 집합 A에, 다른 끝점 v는 집합 B에 속하도록 분할할 수 있는 그래프를 의미합니다. 즉, 어떤 간선도 같은 집합 내부(A→A 또는 B→B)를 연결하지 않아야 합니다.

예시

예를 들어 다음과 같은 그래프가 입력으로 주어진다고 가정해 봅시다.

Python으로 그래프가 이분 그래프(Bipartite Graph)인지 판별하는 프로그램

이 경우 출력은 True입니다. 정점 [0, 4]는 집합 A에, [1, 2, 3]은 집합 B에 속하며, 모든 간선이 A에서 B로 또는 B에서 A로 연결되기 때문입니다.

풀이 접근 방법: DFS 색칠 기법

이 문제는 깊이 우선 탐색(DFS)과 2-색칠(2-coloring) 기법을 활용해 해결할 수 있습니다. 핵심 아이디어는 인접한 정점끼리 서로 다른 색을 칠하고, 만약 이미 색이 칠해진 인접 정점이 현재 정점과 같은 색이라면 이분 그래프가 아니라고 판단하는 것입니다.

알고리즘 단계

  1. 정점 번호를 매개변수로 받는 dfs() 함수를 정의합니다.
  2. graph[source]에 있는 각 인접 정점(child)에 대해 다음을 수행합니다.
    • color[child]가 -1이 아니라면(이미 방문한 정점이라면):
      • color[child]가 color[source]와 같으면 result[0]을 False로 설정하고 함수를 종료합니다.
    • 그렇지 않으면 다음 반복으로 넘어갑니다.
    • 방문하지 않은 정점이라면 color[child]를 1 - color[source]로 설정하여 반대 색을 칠합니다.
    • dfs(child)를 재귀 호출합니다.
  3. 메인 로직에서는 다음을 수행합니다.
    • n := 배열 arr의 크기
    • graph := 정점 0부터 n-1까지의 빈 인접 리스트 생성
    • i를 0부터 n까지 순회하며 arr[i]의 각 j에 대해 graph[j]에 i를 추가하고, graph[i]에 j를 추가합니다(무방향 그래프이므로 양방향 저장).
    • color := 크기 n의 리스트를 -1로 초기화 (-1은 아직 방문하지 않음을 의미)
    • result := True 값을 하나 가진 리스트
  4. i를 0부터 n까지 순회하며 color[i]가 -1인 경우 dfs(i)를 호출합니다. 이 과정은 연결 요소가 여러 개인 그래프도 처리할 수 있게 해줍니다.
  5. 최종적으로 result[0]을 반환합니다.

구현 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

from collections import defaultdict

class Solution:
    def solve(self, arr):
        n = len(arr)
        graph = [set() for i in range(n)]
        for i in range(n):
            for j in arr[i]:
                graph[j].add(i)
                graph[i].add(j)

        color = [-1] * n
        result = [True]

        def dfs(source):
            for child in graph[source]:
                if color[child] != -1:
                    if color[child] == color[source]:
                        result[0] = False
                        return
                    continue
                color[child] = 1 - color[source]
                dfs(child)

        for i in range(n):
            if color[i] == -1:
                dfs(i)
        return result[0]

ob = Solution()
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
print(ob.solve(graph))

입력

graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]

출력

True

동작 원리 정리

이 알고리즘은 각 정점을 0 또는 1의 두 가지 색 중 하나로 칠합니다. DFS를 수행하면서 현재 정점(source)과 인접한 정점(child)에는 항상 반대 색을 부여합니다. 만약 어떤 간선의 양 끝점이 같은 색을 가지게 된다면, 그 그래프는 두 집합으로 나눌 수 없으므로 이분 그래프가 아닙니다.

참고로, 이 방식의 시간 복잡도는 O(V + E)입니다(V는 정점 수, E는 간선 수). 모든 정점과 간선을 한 번씩만 순회하기 때문입니다. 또한 BFS(너비 우선 탐색)를 사용해서도 동일하게 이분 그래프를 판별할 수 있습니다.