관리 메뉴
AYSTORY
algo_lec6 본문
Today’s Topics
- Graph Coloring
- Minimum Spanning Tree (MST)
- Prim’s Algorithm
- Kruskal’s Algorithm
Example 3: Graph Coloring
- 인접한 두 정점에 다른 색을 할당
- 그래프 G=(V,E) 가 주어졌을 때,
색칠 함수 C:V→S (S는 색의 집합)을 찾는 것이 목표. - 제약 조건:
∀(vi,vj) ∈ E, C(vi) ≠ C(vj). - "The chromatic number"
- 그래프를 조건에 맞게 색칠하는 데 필요한 최소 색 개수를 의미.
즉, 가장 효율적으로 색칠했을 때 몇 가지 색만 있으면 되는지를 나타내는 수.- 예:
- 이분 그래프 → 항상 chromatic number = 2
- 완전 그래프 K_n → chromatic number = n
- 예:
- 그래프를 조건에 맞게 색칠하는 데 필요한 최소 색 개수를 의미.
Greedy algorithm
- 각 정점 v_i에 대해:
- 가능한 가장 작은 색 c를 시도
- 인접한 정점들이 c를 쓰고 있으면 c+=1
- 가능한 색을 찾으면 그걸 할당
for i in range(n):
c = 1
while neighbor of v_i is colored with c:
c += 1
color[v_i] = c
Python Example
- graph.adj[u]: 정점 u에 인접한 노드 리스트
- adj_colors: 인접한 정점들이 쓰고 있는 색들의 집합
- result[u]: 정점 u에 할당된 최종 색
def colorGraph(graph, n):
result = {}
for u in range(n):
adj_colors = set([result.get(i) for i in graph.adj[u] if i in result])
color = 1
while color in adj_colors:
color += 1
result[u] = color
- Time complexity: O(VE)
- where V: # of nodes, E: # of edges
- 각 정점에 대해, 인접 정점들(V에 대해 E개 인접리스트 탐색)을 반복하기 때문.
- It doesn't always return an optimal solution.
- Two isomorphic graphs can have different X(G) if we number nodes somewhat differently
- 서로 동형(isomorphic)인 두 그래프도, 정점에 번호를 다르게 붙이면 X(G)가 달라질 수 있음.
- Isomorphic Graphs (동형 그래프):
두 그래프가 구조적으로 동일함. 즉, 정점 간의 연결 방식(형태)은 같고, 정점 번호만 다름. - X(G):
Greedy Coloring 알고리즘이 실제로 사용하는 색의 수를 의미.
이건 chromatic number(진짜 최소 색 수)와는 다름!
- Isomorphic Graphs (동형 그래프):
- 동일한 구조를 가진 그래프(즉, isomorphic)라고 하더라도,
정점의 번호 매기기 순서가 다르면 Greedy 알고리즘의 선택 순서가 달라져서,
실제로 사용하는 색의 수 X(G)X(G)가 달라질 수 있다는 뜻.
- 서로 동형(isomorphic)인 두 그래프도, 정점에 번호를 다르게 붙이면 X(G)가 달라질 수 있음.
Graph Coloring applications: Scheduling
- 위원회 간 중복 인원을 고려하여 회의 시간을 배정
- 각 위원회를 정점으로, 겹치는 인원이 있으면 간선
- 최소 색칠 수 → 최소 시간 슬롯 수
Example 4: Minimum Spanning Tree (MST)
MST란,
- 주어진 무방향 연결 그래프 G=(V,E)에서
- 모든 정점을 포함하고
- 사이클이 없으며
- 간선 가중치의 총합이 최소인 트리를 말함.
MST algorithm 1: Prim’s Algorithm
- MST를 구성할 때, 정점 중심으로 트리를 확장해나가는 Greedy 알고리즘
- 항상 현재까지 만들어진 트리에 가장 가까운 정점을 하나씩 추가하는 방식
- 초기: 임의의 정점 하나 선택
- 항상 가장 가까운 정점을 추가 (locally optimal choice)
- 유사한 방식: Dijkstra’s algorithm
Pseudo-code:
F := ∅
Y := {v₁}
while Y ≠ V:
선택: Y에 가장 가까운 V-Y 정점
그 정점과 연결된 간선을 F에 추가
Python 구현 요약:
- 작동방식
- 임의의 정점 v_1을 시작점으로 선택해 집합 Y에 추가
- Y에 인접한 정점 중, 가장 적은 비용의 간선을 통해 연결된 정점 v를 선택
- 그 정점과 연결된 간선을 MST 집합 F에 추가
- 를 Y에 추가
- 위 과정을 Y=V가 될 때까지 반복
- key[ ]: 최소 연결 비용
- parent[ ]: 각 노드의 부모 저장
- mstSet[ ]: 방문 여부
def primMST(graph):
key = [inf] * V # 최소 연결비용
parent = [None] * V # MST 트리 내에서의 부모
mstSet = [False] * V # MST 포함 여부
key[0] = 0 # 시작 정점 (0번)
parent[0] = -1 # 루트 노드
for _ in range(V):
u = minKey(key, mstSet) # MST에 포함되지 않은 정점 중 key가 최소인 u
mstSet[u] = True # u를 MST에 포함
# u에 인접한 모든 정점 v에 대해
for v in range(V):
if graph[u][v] > 0 and not mstSet[v] and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u- 시간복잡도: O(V²) (인접 행렬 기반)
🔴 초기 상태 (u = 0)
- 시작 정점: 0
- mstSet = [T, F, F, F, F] → 0번 노드만 포함
- key = [0, 2, ∞, 6, ∞]
- 정점 0에서 직접 연결된 노드:
- 1번: 가중치 2 → key[1] = 2
- 3번: 가중치 6 → key[3] = 6
- 정점 0에서 직접 연결된 노드:
- parent = [-1, 0, None, 0, None]
- 1번과 3번은 0번을 통해 연결될 가능성 있음
🔴 단계 2 (u = 1)
- 다음으로 key 값이 가장 작은 1번 정점 선택
- mstSet = [T, T, F, F, F]
- 1번에서 연결된 정점들 업데이트:
- 2번: 3 → key[2] = 3, parent[2] = 1
- 4번: 5 → key[4] = 5, parent[4] = 1
- key = [0, 2, 3, 6, 5], parent = [-1, 0, 1, 0, 1]
🔴 단계 3 (u = 2)
- 가장 작은 key = 3인 정점 2 선택
- mstSet = [T, T, T, F, F]
- 정점 2에서 4로 연결된 간선: 7 (→기존 key[4] = 5는 무시)
- key와 parent는 그대로 유지.
🔴 단계 4 (u = 4)
- 다음 최소 key = 5인 정점 4 선택
- mstSet = [T, T, T, F, T]
- 정점 4 → 3 간선: 9 (→ key[3] = 6은 무시)
🔴 단계 5 (u = 3)
- 마지막 남은 정점 3 선택
- mstSet = [T, T, T, T, T] → MST 완성
🟢 최종 결과: MST 간선 목록
- (0, 1): 2
- (1, 2): 3
- (1, 4): 5
- (0, 3): 6
이 간선들만 따서 보면, 사이클이 없고 모든 정점을 연결하며, 총 가중치도 최소임.
→ Minimum Spanning Tree 완성!
MST algorithm 2: Kruskal’s Algorithm
Kruskal's algorithm이란,
- Greedy 알고리즘 기반의 MST(최소 신장 트리) 구성 방법 중 하나.
- 정점 중심이 아니라 간선 중심으로 MST를 만들어가는 방식.
Pseudo-code:
F := ∅
각 정점을 독립 집합으로 초기화
모든 간선을 가중치 기준 오름차순 정렬
가장 작은 간선부터 선택
- 사이클이 생기지 않으면 간선 추가
모든 정점이 연결되면 종료
- 핵심: Union-Find 자료구조
- 각 정점이 어느 집합(트리)에 속하는지를 추적하는 구조
- find(x): x의 루트(집합 대표)를 찾음
- union(x, y): x, y의 루트를 비교해서 서로 다른 집합이면 합침
- 사이클 여부 판단:
find(x) == find(y) 이면 → 이미 같은 집합 → 이 간선은 사이클 유발함 → ❌
- 모든 간선을 가중치 기준으로 정렬
- 하나씩 간선을 선택하며, 사이클이 생기지 않는 경우에만 MST에 포함
- 정점 수가 개일 때, (n−1)개의 간선이 선택되면 MST 완성
Python 구현:
- find(): root 찾기
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i]) # 경로 압축 (path compression)
return parent[i]
- union(): 랭크(rank)를 이용한 집합 합치기
def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
(이미지 설명)
1️⃣ 서로 다른 높이(ranks)의 트리 병합
- 왼쪽:
- 파란 트리의 루트는 D, rank = 1
- 빨간 트리의 루트는 G, rank = 2
→ 높이가 낮은 트리를, 높이가 더 높은 트리에 붙임
📌 결과:
- 파란 트리 전체가 빨간 트리의 일부가 됨.
- D는 이제 G 아래에 연결됨.
- 전체 트리의 루트는 여전히 G, rank = 2 (변화 없음)
🧠 이유:
- 큰 트리 쪽으로 합치면 전체 트리의 깊이가 늘어나지 않음 → 효율적!
2️⃣ 동일한 높이(ranks)의 트리 병합
- 두 트리 모두 루트(D, E)의 rank = 1
- → 아무 쪽이나 루트가 될 수 있지만,
→ 한 쪽을 다른 쪽에 붙이고 rank를 1 증가시킴
📌 결과:
- 예시에서는 D 트리를 E 트리에 붙임 → E가 새 루트
- E의 rank는 1 → 2로 증가
🧠 이유:
- 두 트리 높이가 같아서 붙이면 루트의 높이가 1 증가함 (정확히 1만 증가!)
- rank 업데이트는 최소화됨
- 시간복잡도: O(E log E) (정렬 포함)
def KruskalMST(graph):
result = []
i, e = 0, 0 # i = index for sorted edges, e = edges in MST
graph.edges.sort(key=lambda x: x[2]) # 간선 가중치로 정렬
parent = [i for i in range(V)]
rank = [0] * V
while e < V - 1:
u, v, w = graph.edges[i]
i += 1
x = find(parent, u)
y = find(parent, v)
if x != y:
e += 1
result.append((u, v, w))
union(parent, rank, x, y)MST Applications
- 전화선/고속도로/파이프라인 설계
- 최소 거리로 모든 지역 연결
- 핵심 목표: 최소 비용으로 전체 연결
'Computer Algorithms' Related Articles
more
