1. 위상 정렬이란?
위상 정렬 (Topology Sort)
- 순서가 정해져 있는 작업 을 차례로 수행해야할 때, 그 순서를 결정해주는 알고리즘
- 순차적으로 어떤 그래프가 형성되어 있을 때, 해당 그래프를 하나의 경로로 표현
- 여러 나열 방법이 있을 수 있기 때문에 답이 다양하게 나올 수 있음
- DAG에만 적용 가능
- DAG : Directed Acyclic Graph, 사이클이 존재하지 않는 방향 그래프
- 위상 정렬은 시작점이 존재해야 하지만, 사이클 그래프에서는 시작점을 찾을 수가 없음
위상 정렬에서 알 수 있는 두 가지
- 현재 그래프가 위상 정렬이 가능한가?
- 위상 정렬이 가능하다면 그 결과는 무엇인가?
2. 위상 정렬 구현
큐를 이용한 방식
- 진입차수가 0인 정점을 큐에 삽입
- 진입차수가 0인 정점이 여러 개 존재할 경우 어느 정점이든 무방
- 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
- 큐에서 원소를 꺼내 연결된 모든 간선을 제거
- 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
- 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
- 큐가 빌 때까지 2번 ~ 3번 과정 반복
- 모든 원소를 방문하기 전에 큐가 빈다면 => 사이클 존재
- 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과
스택을 이용한 방식
- 그래프에서 방문하지 않은 노드면 DFS를 수행
- DFS가 끝나면 해당 노드를 스택에 추가
- 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있음 (역순으로 출력하는 것과 같은 결과)
3. 코드 구현
큐를 이용한 방식
import queue
# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}
def topology_sort_queue(graph):
N = len(graph)
sort_queue = queue.Queue() # 큐
degree = [0 for _ in range(N)] # 진입차수 리스트
for nodes in graph:
for j in graph[nodes]:
degree[j] += 1
print("진입차수 리스트 : ", degree)
for i in range(N):
if degree[i] == 0: sort_queue.put(i)
answer = []
while not sort_queue.empty():
current = sort_queue.get()
answer.append(current)
for i in graph[current]:
degree[i] -= 1
if degree[i] == 0 : sort_queue.put(i)
print("최종 답 : ", answer)
topology_sort_queue(graph)
스택을 이용한 방식
# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}
def topology_sort_stack(graph):
N = len(graph)
stack = [] # 스택
visited = [0 for _ in range(N)] # 방문확인 리스트
for i in graph:
if visited[i] == 0:
dfs(i, stack, visited)
answer = []
while len(stack) != 0:
answer.append(stack.pop())
print("최종 답 : ", answer)
def dfs(v, stack, visited):
visited[v] = 1
for i in graph[v]:
if visited[i] == 0: dfs(i, stack, visited)
stack.append(v)
topology_sort_stack(graph)
#. References