위상 정렬(Topological Sort)

위상 정렬이란, 비순환 방향 그래프를 순서대로 정렬하는 방법이다.

 

1. 위상 정렬 조건

 

* 비순환 : 그래프에 시작과 끝이 존재해야 한다.(순환 가능하면 안된다.)

* 방향성 : 노드들 사이에 방향이 존재해야 한다.

 

2. 위상 정렬 특성

 

* 위상 정렬을 사용하여 정렬된 결과는 여러가지가 있을 수 있다.

 

3. 방법

위와 같은 그래프의 모든 노드를 방향에 따라 순서대로 방문한다고 할 때, 위상 정렬은 아래와 같은 간단한 성질을 이용한다. 

 

특정 노드로 들어오는 간선(Edge)이 없다면, 방문 가능한 상태이다.

 

위의 성질을 이용하여, 아래와 같이 구현할 수 있다.

 

1. 방향 정보를 저장하는 배열을 생성한다.

주어진 방향 정보 : (1 → 2), (2 → 3), (2 → 4), (3 → 4), (4 → 5)

dir_list = [[1, 2],[2,3], [2,4], [3,4], [4,5]]

 

2. 각 노드들로 들어오는 간선의 개수(진입 차수)를 저장한다.

ex) 1번 노드로 들어오는 간선 : 0개

     2번 노드로 들어오는 간선 : 1개

     3번 노드로 들어오는 간선 : 1개

     4번 노드로 들어오는 간선 : 2개

     5번 노드로 들어오는 간선 : 1개

inDegree = [0, 1, 1, 2, 1]

 

3. 빈 큐를 생성하고, 들어오는 간선의 개수가 0인 노드들을 추가한다.

4. (Loop Start) 큐에서 순차적으로 deque한다.

5. deque된 노드에 연결된 간선들을 제거한다.(= inDegree 배열을 업데이트한다.)

6. 각 노드로 들어오는 간선의 개수(진입차수)가 0인 노드를 큐에 추가한다.(Loop End)

5. deque된 순서대로 출력한다.

 

위의 예시로 순차적으로 진행해보자.

 

[t = 0] : 초기 Set-up

1) inDegree 배열에서 들어오는 간선의 수(진입차수)가 0인 노드인 1번 노드를 찾아 큐에 추가한다.

 

 

[t = 1] : Loop Start

1) 큐에서 가장 왼쪽에 있는 노드를(1번 노드) deque한 뒤, 1번 노드에 연결된 간선들을 제거한다.

 

 

2) 들어오는 간선이 0이 된 2번 노드를 큐에 추가한다.

 

[t = 2]

1) 큐에서 가장 왼쪽에 있는 노드를(2번 노드) deque한 뒤, 2번 노드에 연결된 간선들을 제거한다.

 

2) 들어오는 간선이 0이 된 3번 노드를 큐에 추가한다.

[t = 3]

1) 큐에서 가장 왼쪽에 있는 노드를(3번 노드) deque한 뒤, 3번 노드에 연결된 간선들을 제거한다.

 

2) 들어오는 간선이 0이 된 4번 노드를 큐에 추가한다.

 

[t = 4]

1) 큐에서 가장 왼쪽에 있는 노드를(4번 노드) deque한 뒤, 4번 노드에 연결된 간선들을 제거한다.

 

 

2) 들어오는 간선이 0이 된 5번 노드를 큐에 추가한다.

 

[t = 5]

1) 큐에서 가장 왼쪽에 있는 노드를(5번 노드) deque한 뒤, 5번 노드에 연결된 간선들을 제거하려고 보니, 제거할 것이 없다. 그대로 deque한다.

 

 

아래 deque된 노드들을 그대로 출력하면 위상정렬이 완료되었다. 결과는 [1, 2, 3, 4, 5]이다. 

이 그래프의 경우는 답이 한가지밖에 나오지 않지만, 아래와 같은 그래프는 위상정렬하면 여러가지의 결과가 나올 수 있다. 처음 시작을 6에서 해도 되고 1에서 해도 되기 때문이다.

 

 

 

가능한 결과 : [1, 6, 2, 3, 4, 5], [6, 1, 2, 3, 4, 5]

 

위상정렬을 파이썬으로 구현하면 아래와 같다.

 

# n은 노드의 개수, m은 간선의 개수
# 생각의 편의를 위하여 0번 index는 비워놓고 진행

n,m = map(int, r().split())
inDegree = [0 for i in range(n+1)]
dir_list = [[] for i in range(n+1)]

for i in range(m):
    s, e = map(int, r().split())
    dir_list[s].append(e)
    inDegree[e] += 1

q = deque()

while True:
    for i in range(1, n+1):
        if inDegree[i] == 0:
            q.append(i)
    for i in range(1,n+1):
        x = q.popleft()
        answer.append(x)
        for j in dir_list[x]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                q.append(j)
    if not q:
        break
print(*answer)