[알고리즘] Topological Sort

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

• 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다.

• DAG(directed acyclic graph)에서만 사용할 수 있다.

핵심 이론

• 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수

• 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 과정

• 위상정렬은 기본적으로 바로 진행할 수 있는 일, 다시 말해 진입차수가 0인 일을 해결하고 관련된 작업의 진입차수를 1씩 낮추면서 새롭게 진입차수가 0이 된 작업들을 해결하는 식으로 진행한다.

Queue 방법 구현 과정

• queue를 이용하여 진입차수가 0인 작업을 전부 큐에 넣고, 하나씩 팝하면서 해당 작업과 연결되어 있는 작업들의 진입차수를 줄인다.

1. 1번 노드부터 순회하면서 진입차수가 0인 노드를 찾는다.

2. 진입차수가 0인 노드는 Queue에 삽입하고, 해당 노드의 간선들을 모두 제거.(가리키고 있는 노드들의 진입차수를 하나씩 줄인다.)

3. 위 과정을 반복!

Stack 방법 구현 과정

• Stack을 이용한 위상정렬을 위해 필요한 정보는 각 노드들의 방문 여부 (DFS와 동일)

• DFS 과정에서 막다른 노드에 다다르면 뒤로 돌아가면서 스택에 저장 뒤로 돌아가면서 Stack에 넣기 때문에 순서가 느린 노드부터 Stack에 들어가 모든 Stack이 채워지면 Stack을 뒤집어줘야 한다.

Topological Sort 구현

9 9
1 2
2 3
1 4
4 5
5 3
6 4
6 7
7 8
8 9

위와 같은 데이터 입력 형식 (첫째 줄에 노드의 개수 n과 간선의 갯수 m)을 입력하고, 아래 m개 줄에 연결될 노드에 대한 정보들이 있다고 가정해보자.

queue로 구현

• BFS와 비슷한 방식으로 정렬된다.

n, m = map(int, input().split())
indegree = [0]*(n+1)              # 진입차수에 대한 정보를 담은 배열을 생성한다.
                                  # 데이터가 1부터 시작하기 때문에 n+1개를 생성했다.
                                  # 각각의 인덱스는 노드의 숫자에 해당하고 인덱스의 값은 진입차수의 개수를 의미한다.

graph = [[] for _ in range(n+1)]  # 각 노드별로 나가는 간선의 위치를 저장한다.
                                  # 각 인덱스는 노드의 숫자에 해당하고 인덱스의 값에 해당하는 배열으로 간선이 이어진다는 것을 의미한다.
                                  # 아래의 반복문을 통해 채워질 것이다.

queue = []                        # 진입차수가 없는 노드가 들어갈 queue 자료구조이다.
result = []                       # queue에서 빠져나온 순서대로 값이 들어갈 것이며, 이것이 정렬의 결과물이다.

for _ in range(m):
  prev, post = map(int, input().split()) # prev는 선행과목, post는 후수과목에 해당한다.
  graph[prev].append(post)        # graph의 prev인덱스에 해당하는 배열에 post를 추가한다. 즉, prev라는 과목이 수강되어야 post를 수강할 수 있다.
  indegree[post]+= 1              # post의 선수과목이 지정되었으므로 진입차수를 1 추가한다.

for i in range(1, n+1):           # 처음에는 먼저 진입차수가 0인 노드부터 찾습니다.
  if indegree[i] == 0:
    queue.append(i)


while queue:                      # queue가 비게 된다면, 정렬이 모두 끝납니다. 그래프 내에 사이클이 존재한다면, queue 가 비지 않게 되고 무한루프를 돕니다.
  value = queue.pop(0)            # queue에서 값을 꺼냅니다.
  result.append(value)            # 결과값으로 저장합니다.
  for i in graph[value]:          # queue에서 꺼내진 값의 다음 노드로 연결된 노드들을 찾습니다.
    indegree[i] -= 1              # queue에서 꺼내진 값에서 나오는 진출간선을 없애줍니다.
    if indegree[i] == 0:          # 이후 진입차수가 0이 된 노드를 찾고
      queue.append(i)             # 해당 노드를 queue에 넣고 queue가 빌 때까지 위의 내용들을 반복합니다.

print(result)

stack으로 구현

• DFS와 비슷한 방식으로 정렬된다.

n, m = map(int, input().split())
indegree = [0]*(n+1)              # 진입차수에 대한 정보를 담은 배열을 생성한다.
                                  # 데이터가 1부터 시작하기 때문에 n+1개를 생성했다.
                                  # 각각의 인덱스는 노드의 숫자에 해당하고 인덱스의 값은 진입차수의 개수를 의미한다.

graph = [[] for _ in range(n+1)]  # 각 노드별로 나가는 간선의 위치를 저장한다.
                                  # 각 인덱스는 노드의 숫자에 해당하고 인덱스의 값에 해당하는 배열으로 간선이 이어진다는 것을 의미한다.
                                  # 아래의 반복문을 통해 채워질 것이다.

stack = []                        # 진입차수가 없는 노드가 들어갈 stack 자료구조이다.
result = []                       # stack에서 빠져나온 순서대로 값이 들어갈 것이며, 이것이 정렬의 결과물이다.

for _ in range(m):
  prev, post = map(int, input().split()) # prev는 선행과목, post는 후수과목에 해당한다.
  graph[prev].append(post)        # graph의 prev인덱스에 해당하는 배열에 post를 추가한다. 즉, prev라는 과목이 수강되어야 post를 수강할 수 있다.
  indegree[post]+= 1              # post의 선수과목이 지정되었으므로 진입차수를 1 추가한다.

for i in range(1, n+1):           # 처음에는 먼저 진입차수가 0인 노드부터 찾습니다.
  if indegree[i] == 0:
    stack.append(i)


while stack:                      # stack 비게 된다면, 정렬이 모두 끝납니다. 그래프 내에 사이클이 존재한다면, stack dl 비지 않게 되고 무한루프를 돕니다.
  value = stack.pop()            # stack에서 값을 꺼냅니다.
  result.append(value)            # 결과값으로 저장합니다.
  for i in graph[value]:          # stack에서 꺼내진 값의 다음 노드로 연결된 노드들을 찾습니다.
    indegree[i] -= 1              # stack에서 꺼내진 값에서 나오는 진출간선을 없애줍니다.
    if indegree[i] == 0:          # 이후 진입차수가 0이 된 노드를 찾고
      stack.append(i)             # 해당 노드를 stack에 넣고 stack가 빌 때까지 위의 내용들을 반복합니다.

print(result)