동빈나님의 27강 - 위상정렬을 보고 정리한 내용입니다.

위상정렬이란 ?

순서가 정해진 작업을 차례대로 수행할때 그 순서를 알기 위해 사용하는 알고리즘

• 여러개의 답이 존재할 수 있음
• DAG에만 적용이 가능하다.
  -> DAG란? Directed Acyclic Graph - 방향이 있고 사이클이 없는 그래프
  -> 시작점이 있어야 하므로 사이클이 발생하면 위상정렬 수행 x

위상정렬의 방법

queue를 사용하는 방법과 stack을 사용하는 방법이 있는데 queue를 사용하는 방법을 알아보자.

백준 1005 - ACM craft의 예시로 살펴보자.

1. 진입차수가 0인 노드를 queue에 삽입한다.
   -> 진입차수란? 해당 node로 들어오는 간선의 개수 즉, node를 만족하는 조건의 개수이다.

   예시에서 각 노드의 진입차수는 아래와 같다.

   
   진입차수가 0인 노드1을 큐에 삽입한다.

2. queue에서 원소를 꺼내서 해당 원소와 연결된 모든 간선을 제거한다.

3. 진입차수가 0이 된 정점을 queue에 삽입한다.
   -> 여기서는 노드 2와 3이 진입차수가 0이 된 정점이다.

4. queue가 빌때까지 2,3을 반복한다.
   -> 모든 원소를 방문하기 전에 queue가 비면 cycle이 존재해서 위상정렬을 수행할 수 x, 아니면 queue에서 꺼낸 순서가 위상정렬을 수행한 순서가 된다.

위의 예제를 이 알고리즘대로 수행하면 아래와 같은 순서로 진행된다.

모든 원소를 방문한 후에 queue가 비었고, 이때 queue에서 꺼낸 순서 1,2,3,4가 위상정렬을 한 결과가 된다.

python 코드

from collections import deque
#indegree[i] : i의 진입 차수
#answer = [] : 위상정렬의 결과가 담긴 배열

def topologiSort():
    queue = deque()

    # 1. 진입차수가 0인 노드 전부 queue에 넣기
    for i in range(N):
        if indegree[i] == 0:
            queue.append(i)
    
    # 위상정렬 수행하기
    for i in range(N):
        # 모든 노드 방문 전에 큐가 비면 -> cycle이 있는 그래프
        if not queue:
            return False
        
        current = queue.popleft()
        answer.append(current)  #위상정렬 결과 리스트에 추가

        # 2. 인접한 정점 순회하면서 간선 제거하기
        for next in adj[current]:
            indegree[next] -= 1
            # 3. 진입차수 0인 node queue에 넣기
            if indegree[next] == 0:
                queue.append(next)
    
    return True

출처

나동빈님의 27강 - 위상정렬
https://ekdbsl22.tistory.com/46