그래프를 사용하는 알고리즘은 뭐가 있을까? - 크루스칼, 프림, 위상 정렬
https://seclab-j.tistory.com/86
그래프 이론 요약 정리
그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다. 차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 그래프는
seclab-j.tistory.com
앞선 정리 내용에서는 코드로 그래프를 어떻게 표현하는가를 중점적으로 살펴보았다. (인접 행렬과 인접 리스트..)
오늘은 여기서 좀 더 나아가 그래프를 사용하는 알고리즘에는 무엇이 있으며 어떻게 사용하는지에 대해서 다루어 보고자 한다.
먼저 복잡도를 언급해보자면 다음과 같다.
| 알고리즘 종류 | 시간 복잡도 |
| 크루스칼 알고리즘 | O(ElogE) |
| 프림 알고리즘 | O(VlogV) |
| 위상 정렬 | O(V + E) |
시작하기에 앞서 - 서로소 집합 자료구조(Disjoint Sets)
그래프를 기반으로 하는 알고리즘은 결국 union 연산과 find 연산을 중심적으로 진행하게 된다. 그리고 두 연산을 내포하고 있는 자료구조를 서로소 집합 자료구조라고 부른다.
- union 연산 : 두 집합을 합치는 연산
- find 연산 : 집합들 중에서 특정 원소가 존재하는 집합을 찾는 연산
서로소 집합 자료구조란 서로소 부분 집합으로 이루어진 데이터를 처리하기 위한 자료구조이며 새로운 자료구조를 사용하는 것은 아니고 트리 자료구조로 집합을 표현한다.
그렇다면 union 연산과 find 연산은 트리 자료구조로 어떻게 구현할까?
원소 = {1, 2, 3, 4, 5} 일때 (4, 5), (3, 4), (2, 3), (1, 2)의 union 연산을 해야한다고 하자.
먼저 트리 자료구조를 사용하기 때문에 각 원소 개수와 동일한 parent table을 하나 만든다. 그리고 해당 테이블은 일단 원소가 자기 자신을 parent로 가리키도록 초기화해둔다.
|
1
2
3
|
import copy
v = [1, 2, 3, 4, 5]
parent = copy.deepcopy(v)
|
cs |
union 연산은 각 집합에 해당하는 트리를 연결리스트처럼 연결하는 합집합 연산이라고 보면 편하다.
두 집합을 합칠 때는 주로 더 작은 원소가 부모 노드라고 가정한다.
이 때 매 union 연산 마다 연산을 하는 두 대상 집합의 루트 노드를 파악하기 위해서는 find 연산을 수행해야 한다. 일단 union 연산 코드는 다음과 같다. 해당 함수를 사용할 때는 union(parent 테이블, 4, 5) 와 같이 사용하면 되고
|
1
2
3
4
5
6
7
|
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
|
cs |
find 연산은 각 집합의 가장 루트 노드를 찾는 연산으로 구현상 현재 노드와 부모 노드가 동일할 경우를 찾아 부모 노드를 계속 따라간다고 보면 된다. 코드는 다음과 같다.
|
1
2
3
4
|
def find(parent, x):
if parent[x] != x:
return find(parent, parent[x])
return parent[x]
|
cs |
이때 union 연산시 우리는 사실상 모든 부모 노드가 아니라 루트 노드만을 찾으면 되기 때문에 다음과 같이 경로 압축 기법으로 구현하는 것이 더 효율적이라고..
|
1
2
3
4
|
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
|
cs |
위의 코드처럼 구현하면 parent가 가리키는 것은 부모 노드가 아니라 최상위의 루트 노드를 가리키게 된다.
신장트리와 사이클 확인하기
신장트리는 모든 노드를 포함하면서도 노드 간의 사이클이 존재하지 않는 트리를 의미한다.
물론 정식 의미는 방향성이 없는 그래프에서 모든 정점을 포함하되 사이클이 존재하지 않도록 구성한 부분 그래프를 의미한다.
이때 신장트리의 사이클 존재 여부는 앞선 서로소 집합 자료구조의 find를 통해 확인할 수 있으며 union 연산을 통해 신장트리를 구성할 수 있다.
그리고 이를 코드로 나타내면 다음과 같다.
|
1
2
3
4
5
6
7
8
9
|
cycle = False
union_edge = ((4, 5), (1, 3))
for a, b in union_edge:
if find(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union(parent, a, b)
|
cs |
크루스칼 알고리즘 - 서로소 집합 자료구조 + 그리디 알고리즘
앞서 트리를 사용한 알고리즘 문제에는 주로 최소한의 비용으로 신장트리(Spanning Tree)를 찾는 문제가 많이 출제된다고 언급한 바 있다.
이러한 문제는 주로 크루스칼 알고리즘으로 풀게 되는데 크루스칼 알고리즘은 결국 신장 트리를 그리디 알고리즘으로 푸는 알고리즘이다. 그리고 신장 트리의 사이클 유무 판별은 서로소 집합 자료구조를 통해 판별할 수 있다.
간단하게 크루스칼 알고리즘을 푸는 방법을 정리해보자면
1. edge 데이터를 비용에 따라서 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 사이클 여부를 확인한다. (사이클이 존재하지 않을 경우에만 신장 트리에 포함)
3. 모든 간선에 대하여 반복
|
1
2
3
4
5
6
7
8
9
10
11
12
|
edges = []
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find(parent, a) != find(parent, b):
union(parent, a, b)
result += cost
|
cs |
프림 알고리즘 - 우선순위 큐 + 서로소 집합 알고리즘
프림 알고리즘의 경우 임의의 정점이 주어져 고정된 채로 해당 정점에서 시작해서 최소 비용의 신장 트리를 구성하는 방법이다.
때문에 크루스칼과는 달리 정렬은 진행하지 않으며 힙을 사용해서 신장트리를 구성하게 된다.
프림 알고리즘을 푸는 방법을 정리해보자면
1. 임의의 정점을 선택하여 최소 신장 트리에 추가하고, 해당 전점과 연결된 모든 간선을 우선순위 큐에 추가함
2. 우선순위 큐에서 비용이 가장 작은 간선을 pop. 해당 간선이 연결하는 정점이 사이클을 구성하는지 확인 (존재여부 확인) - 신장트리에 존재하지 않을 경우에만 추가 - 마찬가지로 연결된 모든 간선을 우선순위 큐에 추가
3. 최소 신장 트리에 V-1개의 간선이 추가될 때까지 반복
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import heapq
def prim():
result = []
q = [edges[0]]
heapq.heapify(q)
for i in range(1, v + 1):
while q:
cost, a, b = q.popleft()
if find(parent, a) != find(parent, b):
union(parent, a, b)
result += cost
|
cs |
위상정렬(Topology Sort) - 우선순위 큐
위상 정렬은 순서가 정해져 있는 작업을 차례대로 수행해야할 때 사용하는 정렬 방식으로
방향 그래프의 모든 노드들이 방향성에 거스르지 않도록 나열할 때 사용되는 알고리즘이다.
1. 진입차수가 0인 노드를 큐에 입력한다.
2. 큐에서 노드를 꺼내 해당 노드에서 출발한 간선을 모두 제거한다. (도착 노드의 indegree 차수를 하나 줄임)
3. 도착하는 노드들 중 진입차수가 0인 노드를 다시 큐에 입력한다. 이는 큐가 빌때까지 반복된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
from collections import deque
def topology_sort():
result = []
q = deque()
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
for i in graph[now]:
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
|
cs |
Reference
- BaarkingDog 블로그 https://blog.encrypted.gg/1016
- 이것이 취업을 위한 코딩 테스트다. with 파이썬
'알고리즘 > 이론' 카테고리의 다른 글
| 플로이드 워샬 알고리즘 요약 정리 (0) | 2023.05.27 |
|---|---|
| 재귀 (== 분할정복) (0) | 2023.05.17 |
| 그래프 이론 요약 정리 (0) | 2023.03.27 |
| 동적 계획법, 다이나믹 프로그래밍 (0) | 2023.03.07 |
| [알고리즘 파이썬편] 큐와 힙의 사용법 (0) | 2022.02.20 |