Topology Sort
위상정렬이란?
방향 그래프에서 노드의 선후 관계를 유지하면서 정렬하는 알고리즘
사용 예시
•
강의 수강 순서(선수 과목)
•
작업 빌드 순서(컴파일 순서)
위상정렬 구현
조건
•
DAG(Directed Acyclic Graph) : 방향이 있고 사이클이 없는 그래프
◦
사이클 : 어떤 노드에서 출발해서 다시 자기 자신으로 돌아오는 경로가 존재하는 경우
•
위상정렬은 반드시 DAG에서만 가능(사이클이 존재하면 실패)
•
진입차수(In-degree)를 이용해 구현
◦
진입차수 : 특정 노드로 들어오는 간선의 개수
구현방법
1. BFS(Kahn’s Algorithm)
1.
모든 노드의 진입차수를 구하기
2.
진입차수가 0인 노드를 큐에 삽입
3.
큐에서 노드를 꺼내 결과에 추가하고, 이 노드가 가리키는 노드들의 진입차수를 1씩 줄이기
4.
진입차수가 0이 된 노드를 큐에 다시 삽입
5.
큐가 빌 때까지 반복
2. DFS
1.
방문하지 않은 노드에서 DFS 시작
2.
DFS 재귀 호출이 끝난 노드를 스택에 삽입
3.
모든 노드에 대해 DFS 종료 후, 스택에서 꺼내면서 출력
참고 자료
코드로 확인해볼까요?
BFS(Kahn’s Algorithm)
from collections import deque
def topolgy_sort_bfs(verticles, edges):
in_degree = [0] * verticles # 진입차수
graph = [[] for _ in range(verticles)] # 인접리스트 방식
for u,v in edges:
graph[u].append(v)
in_degree[v] += 1 # u -> v 방향이니까, v의 진입차수가 1증가
order_result = []
# 진입차수가 0인 노드들 큐에 삽입
queue = deque([i for i in range(verticles) if in_degree[i] == 0])
while queue:
node = queue.popleft() # 큐에서 진입차수가 0인 노드 꺼내기
order_result.append(node)
for neighbor_node in graph[node]:
in_degree[neighbor_node] -= 1
if in_degree[neighbor_node] == 0:
queue.append(neighbor_node)
print(' '.join(map(str, order_result)))
Python
복사
보통 알고리즘 문제에서는…
from collections import deque
v, e = map(int, input().split())
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)
indegree[b] += 1
def topology_sort_bfs(v, graph, indegree):
result = [] # 정렬 결과 내용
queue = deque([i for i in range(1, v+1) if in_degree[i] == 0])
while queue:
node = queue.popleft()
result.append(node)
for next_node in graph[node]:
in_degree[next_node] -= 1
if in_degree[next_node] == 0:
queue.append(next_node)
# 정렬된 결과 반환
return result
result = topology_sort_bfs(v, graph, indegree)
print(' '.join(map(str, result)))
Python
복사
DFS
재귀
v, e = map(int, input().split())
graph = [[] for i in range(v + 1)]
visited = [False] * (v+1)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
def dfs(node, graph, visited, result):
visited[node] = True
for neighbor in graph[node]:
if not visited[node]:
dfs(node, graph, visited, result)
result.append(node) # 후위순회 : 모든 자식 처리 후 현재 노드 추가
def topology_sort_dfs_recursive(v, graph, visited):
result = []
for node in range(1, v+1):
if not visited[node]:
dfs(node, graph, visited, result)
# 정렬된 결과 반환
result.reverse() # # 후위 순회 결과를 뒤집어서 위상정렬 순서 완성
return result
result = topology_sort_dfs_recursive(v, graph, visited)
print(' '.join(map(str, result)))
Python
복사
스택
v, e = map(int, input().split())
graph = [[] for i in range(v + 1)]
visited = [False] * (v+1)
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b)
def topology_sort_dfs_explicit_stack(v, graph, visited):
result = []
stack = []
for start in range(1, v+1):
if not visited[start]:
temp_stack = [(start, False)]
while temp_stack:
node, processed = temp_stack.pop()
if processed:
result.append((node, True))
else:
visited[node] = True
temp_stack.append((node, True))
for neighbor in reversed(graph[node]):
if not visited[neighbor]:
temp_stack.append((neighbor, False))
# 정렬된 결과 반환
result.reverse() # # 후위 순회 결과를 뒤집어서 위상정렬 순서 완성
return result
result = topology_sort_dfs_recursive(v, graph)
print(' '.join(map(str, result)))
Python
복사