이분그래프

이분 그래프 판별 알고리즘 설명

1. 이분 그래프란?

이분 그래프(Bipartite Graph)는 그래프의 정점들을 두 그룹으로 나눌 수 있어서, 각 그룹 내의 정점들 사이에는 간선이 없는 그래프를 말합니다.

2. 알고리즘 흐름도

3. BFS를 이용한 색칠 과정

이분 그래프와 관련 알고리즘

 

 

4. 코드 구현 설명

주요 구현 단계:

1. 그래프 생성

   
               graph = [[] for _ in range(v + 1)]
               for u, w in edges:
                   graph[u].append(w)
                   graph[w].append(u)
               

2. 색상 배열 초기화

   
               colors = [0] * (v + 1)  # 0: 미방문, 1: 그룹1, -1: 그룹2
               

3. BFS 탐색

   
               from collections import deque
               
               def bfs(start):
                   queue = deque([start])
                   colors[start] = 1
                   while queue:
                       node = queue.popleft()
                       for neighbor in graph[node]:
                           if colors[neighbor] == 0:
                               colors[neighbor] = -colors[node]
                               queue.append(neighbor)
                           elif colors[neighbor] == colors[node]:
                               return False
                   return True
               

5. 시간 복잡도

전체 알고리즘의 시간 복잡도는 O(V + E)입니다.

• V: 정점의 개수
• E: 간선의 개수
• 각 정점과 간선을 한 번씩만 방문