[알고리즘] ✨ 그래프 이론: 크루스칼 알고리즘 (Kruskal Algorithm), 위상 정렬(Topology Sort)
본 포스팅은
이것이 취업을 위한 코딩테스트다 - 나동빈
책을 통해 공부한 내용을 토대로 작성하였습니다.
크루스칼 알고리즘 (Kruskal Algorithm)
크루스칼 알고리즘은 대표적인 '최소 신장 트리(MST, Minimum Spanning Tree)' 알고리즘 중 하나이다
✋ 신장 트리
- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
신장트리가 왜 필요할까? 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장트리를 찾아야 할 때가 있다.
ex) N개의 도시가 있을 때 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우, 최소한의 비용으로 모든 도시를 '연결'하고자 할 때!
✨ 크루스칼 알고리즘
- 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.
- 그리디 알고리즘으로 분류됨
- 최종적으로 신장 트리에 포함되는 간선의 개수: 노드개수 - 1
✨ 구현
가장 거리가 짧은 간선부터 차례대로 집합에 추가
1️⃣ 모든 간선을 비용에 따라 오름차순 정렬
2️⃣ 가장 거리가 짧은 간선부터 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인
1) 사이클 X → 최소 신장 트리에 포함시킴
2) 사이클 O → 최소 신장 트리에 포함 x
3️⃣ 모든 간선에 대하여 2️⃣ 번 반복
✨ 소스코드
# 특정 원소가 속한 집합 찾기
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
# 노드의 개수와 간선(union)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블에서 부모노드를 자기자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# 모든 간선 정보 입력받기
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(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
위상 정렬(Topology Sort)
✋ 위상 정렬
위상 정렬이란 지금까지의 정렬은 '수'를 정렬해오던 것이었다면 위상 정렬은 '그래프'를 정렬하는 것이다. 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
😃 결국 작업의 순서가 정해져 있을 때 작업을 정확하게 정렬해주는 알고리즘
✨ 위상 정렬의 조건
DAG(Directed Acyclic Graph) 방향성 비순환 그래프이어야 한다. (방향성은 있으면서 사이클은 없는 그래프)
✨ 위상정렬 알고리즘
1️⃣ 진입차수가 0인 노드를 큐에 넣는다.
2️⃣ 큐가 빌 때까지 다음의 과정을 반복한다.
1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
✨ 소스코드
from collections import deque
# Vertex, Edge 입력 받기
v, e = map(int, input().split())
# 모든 노드에 대한 indegree 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for i in range(v + 1)]
# 방향 그래프의 모든 간선 정보 입력받기
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # A -> B 로 이동 가능
indegree[b] += 1 # 진입 차수 올려주기
def topology_sort():
result = []
q = deque()
# 처음 시작할 때 진입차수가 0인 노드 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
topology_sort()
✨ 시간 복잡도
시간 복잡도는 O(V+E)이다. 위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서,
해당 노드에서 출발하는 간선을 차례대로 제거
결과적으로 노드와 간선을 모두 확인하기 때문 O(V+E)의 시간 소요
Author And Source
이 문제에 관하여([알고리즘] ✨ 그래프 이론: 크루스칼 알고리즘 (Kruskal Algorithm), 위상 정렬(Topology Sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@syoung125/알고리즘-그래프-이론-크루스칼-알고리즘-Kruskal-Algorithm-위상-정렬Topology-Sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)