📌 그래프는 자료구조편과 알고리즘편, 알고리즘-최단경로편, 코드편 총 4편으로 나누어서 작성
본격적으로 정리하기 전에 그래프 알고리즘에는 어떤게 있나, 하고 찾아봤더니 n년전에 학교에서 배우고 기억 저편으로 넘어갔던 알고리즘들의 어렴풋한 이름들이 우르르 나오면서 뭐가 뭔지 모르겠어서 분류를 해봤다.
- 그래프 내의 모든 정점을 순회하는 알고리즘
- DFS (완료)
- BFS (완료)
- 최소 신장 트리를 만드는 알고리즘
- 크루스칼 알고리즘
- 프림 알고리즘
- 그래프 상에서 최단경로를 탐색하는 알고리즘
- 다익스트라 알고리즘
- 벨만 포드 알고리즘
- 플로이드 워셜 알고리즘
- 작업 사이에 특정 의존(순서)관계가 있을때 이를 정렬하는 알고리즘
- 위상정렬 알고리즘
(3번 최단경로 알고리즘은 나중에 따로 주제를 빼서 작성할 예정)
우선 시작하기 전에 그래프 알고리즘에서 중요한 개념인 서로소 집합과 최소신장트리에 대해 알아보자.
서로소 집합 자료구조는 기본적으로 트리 자료구조를 사용한다.
union
연산을 확인하고, 합치려는 두 노드 A
, B
를 확인한다.A
의 루트노드 A'
와 B
의 루트노드 B'
를 찾는다.A'
를 B'
의 부모 노드로 설정한다.union
연산을 처리할 때까지 1~3번 과정을 반복한다.cf) 부모노드를 저장하는 테이블의 초기값은 자기 자신이다.
# find
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# union
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
💡 a와 b를 합칠 때 a의 부모를 b로(b의 부모를 a로) 바꾸는게 아니라, a의 부모의 부모를 b의 부모로(b의 부모의 부모를 a의 부모로) 바꾸는 것에 주의한다.
서로소 집합은 무방향 그래프에서 사이클을 판별할때 사용할 수 있다.
for e in {모든 간선} :
a, b = {간선 e에 포함된 두 노드}
if find_parent(parent, a) == find_parent(parent, b):
{사이클 발생}
break
else:
union_parent(parent, a, b)
edges = [가중치에 따라 오름차순 정렬된 모든 간선]
parent = [부모 테이블]
total_cost = 0 # 최소신장트리의 가중치
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
for i in range(간선개수):
cost, a, b = edges[i]
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
total_cost += cost
# 사이클이 발생하지 않았으므로 이번 edges[i]는 최소신장트리에 포함됨
find_parent
와 union_parent
함수를 이용해서 확인할 수 있다.코테에서 많이 쓰는 알고리즘은 아닌거 같아서 구현은 생략 (절대 귀찮아서 안하는거 아님)
위상정렬은 큐를 이용하여 구현한다.
각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과다.
v = {노드개수}
indegree = [모든 노드에 대한 진입차수]
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 g in graph[now]:
indegree[g] -= 1
if indegree[g] == 0:
q.append(g)
return result