위상정렬 알고리즘(Topology sort Algorithm)

Gyuhan Park·2022년 1월 24일
1

알고리즘 뿌시기

목록 보기
5/9

위상정렬 알고리즘이란?

사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것
ex) 대학교 선수과목 이수체계도

[위상정렬 알고리즘을 쓸 수 있는 조건]
1. 방향이 있는 그래프
2. 사이클이 없는 그래프
즉, 사이클이 없는 방향 그래프라 할 수 있는데 이를 DAG(Direct Acyclic Graph)라고도 한다.
DAG인 경우 위상정렬 알고리즘을 사용할 수 있다.

알고리즘 실행 과정

핵심은 각 노드의 진입차수(indegree)를 구하고 이를 통해 순서를 정하는 것이다.
진입차수란 화살표의 끝이 해당 노드에 들어오는 수다.
예를 들어 A -> B 그래프가 있다면 A의 진입차수는 0이고 B의 진입차수는 1이다.

그래서 맨처음 진입차수가 0인 노드가 루트노드이므로, 루트노드부터 화살표를 하나씩 지우는 작업을 통해 알고리즘이 구현된다.

A -> B -> C 그래프가 있을 때 루트노드 A를 결과 리스트에 넣고 연결된 화살표를 지우면 B의 진입차수가 1에서 0으로 줄어드므로 탐색 대상이 되는 것이다. 이를 큐에 넣어주는 작업을 그래프가 끝날 때까지 해주면 된다.

[요약]
1. 진입 차수가 0인 노드를 큐에 삽입한다.
2. 큐에서 원소를 꺼내 해당 원소에 연결된 화살표를 제거한다.
3. 화살표를 제거한 후 진입 차수가 0이 된 노드를 큐에 삽입한다.
4. 위 과정을 반복한다.

위상정렬 특징

  • 시간복잡도 : O(V+E)

  • 아래와 같이 큐로 구현가능하고, DFS를 이용하면 스택으로도 구현할 수 있다.

  • 큐에 한번에 2개 이상이 들어가는 경우 순서가 달라지므로 결과값이 여러개가 될 수 있다.

위상정렬 코드 (queue)

import sys
from collections import deque
input = sys.stdin.readline

V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]
indegree = [0] * (V+1)

for i in range(E):
  a, b = map(int, input().split())
  graph[a].append(b) # a -> b
  indegree[b] += 1 # b의 진입차수 증가


def topology_sort():
  result = []
  queue = deque()
  # 진입차수가 0인 노드 찾기(그래프의 맨처음 찾기)
  for i in range(1, V+1):
    if indegree[i] == 0:
      queue.append(i)
  
  while queue:
    cur = queue.popleft()
    result.append(cur)
    # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
    for i in graph[cur]:
      indegree[i] -= 1
      if indegree[i] == 0:
        queue.append(i)
  

  for i in result:
    print(i, end=' ')

topology_sort()

위상정렬 코드 (stack + DFS)

  1. 그래프에서 방문하지 않은 노드면 DFS를 수행
  2. DFS가 끝나면 해당 노드를 스택에 추가(정렬된 노드)
  3. 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있음
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
graph = [[] for _ in range(V+1)]

for i in range(E):
  a, b = map(int, input().split())
  graph[a].append(b) # a -> b

def topology_sort():
    N = len(graph)
    stack = [] 
    visited = [0 for _ in range(N)] 
    for i in range(1, N):
      if visited[i] == 0:
          dfs(i, stack, visited)
    
    result = []
    while len(stack) != 0:
        result.append(stack.pop())
    for i in result:
      print(i, end=' ')

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()
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글