그래프의 노드를 정렬하는 위상정렬 정복하기

1. 개요

 

위상 정렬(topology sort)은 정렬 알고리즘의 일종

 

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘

 

이론적으로, 위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.

 

실제 예를 들어 위상 정렬을 수행하는 전형적인 예시는, '선수과목을 고려한 학습 순서 결정'이 있다.

 

예를 들어 컴퓨터공학과 커리큘럼에는 '자료구조'과목을 수강한 뒤에, '알고리즘'강의를 수강하는 것을 권장한다.

 

이 경우에 자료구조와 알고리즘을 각각 노드로 표현하고, 자료구조에서 알고리즘으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다.

 

그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

 

만약 컴퓨터공학과의 커리큘럼이 자료구조, 알고리즘, 고급 알고리즘으로 구성되어 있다고 하자

 

알고리즘의 선수과목으로 자료구조, 고급 알고리즘의 선수과목으로 자료구조와 알고리즘이 있다.

 

 

 

만약 모든 과목을 수강하고 싶다면, 자료구조 > 알고리즘 > 고급 알고리즘 순서로 강의를 수강해야한다.

 

2. 진입차수(indegree)

 

특정한 노드로 들어오는 간선의 개수

 

위 그림에서 '고급 알고리즘'의 진입차수는?

 

알고리즘 > 고급 알고리즘과 자료구조> 고급 알고리즘이 있으므로, 들어오는 간선의 개수는 2이고 그래서 진입차수는 2이다.

 

3. 위상 정렬 알고리즘

 

3-1) 진입차수가 0인 노드를 큐에 넣는다.

 

3-2) 큐가 빌 때까지 다음을 반복한다.

 

3-2-1) 큐에서 해당 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거

 

3-2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

 

3-3) 큐에서 원소를 꺼낸 순서를 기억해놓는다. 모든 노드를 처리했을 경우, 그 과정동안 원소를 꺼낸 순서가 위상 정렬을 수행한 결과이다.

 

알고리즘에서 확인할 수 있듯이 큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복한다

 

 

-----------------------------------------------------------------------------------------------------------------------------

이 때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다

 

다시 말해 큐에서 원소가 v번(노드의 개수) 추출 되기 전에 큐가 비어버리면 사이클이 발생한 것이다.

 

사이클이 있는 경우, 사이클에 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문이다

 

 

1,2,3,4가 사이클인데, 진입차수가 0인 6번을 넣고, 다음에 5번을 넣고, 처리하더라도 1,2,3,4는 진입차수가 0이 아니니까

 

큐에 들어가지 못함

 

기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 가정하는 경우가 많아 그런 경우를 먼저 공부하도록 한다.

(물론 발생하는 경우 매우 어려운 문제가 된다)

 

-----------------------------------------------------------------------------------------------------------------------------

 

4. 예시를 통해 이해하는 위상정렬

 

다음 그래프에서 위상정렬을 수행해보자.

 

 

먼저 초기 단계에서는 진입차수가 0인 노드를 큐에 넣는다.

 

현재 노드 1의 진입차수만 0이기 때문에, 큐에 노드 1만 삽입한다.

 

 

다음, 큐에 들어간 노드 1을 먼저 꺼낸다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1"

 

이제 노드 1에서 출발하는 간선들을 모두 제거한다. 

 

 

그러면 노드 2, 노드 5의 진입차수가 0이 된다. 진입차수가 0이 된 노드들을 큐에 넣는다.

 

그리고 큐에 들어간 노드 2를 꺼낸다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2"

 

그 후 노드 2에서 출발하는 간선들을 모두 제거한다.

 

 

 

그러면, 3번이 새롭게 진입차수가 0이 되고 이것을 큐에 넣는다.

 

그 후 노드 5를 큐에서 꺼내고 노드 5에서 출발하는 간선을 모두 제거한다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2>5"

 

 

 

그러면 노드 6의 진입차수가 0이된다. 그러면 노드 6을 새롭게 큐에 넣어준다.

 

그리고 노드 3을 꺼내서 노드 3에서 출발하는 간선들을 제거한다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2>5>3"

 

 

이번에는 진입차수가 0이 되는 노드가 존재하지 않으니 넘어간다. 다시 노드 6을 큐에서 꺼내고,

 

노드 6에서 출발하는 간선들을 모두 제거한다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2>5>3>6"

 

 

그러면 새롭게 노드 4가 진입차수가 0이 되고 이것을 큐에 다시 넣어준다.

 

그리고 큐에서 노드 4를 꺼내서, 노드 4에서 출발하는 간선들을 모두 제거한다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2>5>3>6>4"

 

 

그러면 노드 7이 진입차수가 0이 되고, 이것을 다시 큐에 넣어준다.

 

그리고 큐에서 노드 7을 꺼내고 7에서 출발하는 간선들을 모두 제거한다.

 

그러면 큐에서 빠져나간 노드의 순서는 "1>2>5>3>6>4>7"

 

하지만 7에서 연결된 간선은 존재하지 않으니 넘어간다.

 

그러면 "그래프 상에서 모든 선후 관계를 지키는 노드의 순서"는 어떻게 구하는가?

 

위 과정을 수행하는 동안에, 큐에서 빠져나가는 노드 순서가 위상 정렬을 수행한 결과이다.

 

위상정렬을 수행한 결과는 여러가지가 될 수 있다.

 

큐에 원소가 2가지 이상 들어갈때, 어떤 노드를 먼저 빼느냐에 따라 결과가 달라질 수 있기 때문이다.

 

하나의 결과는 "1>2>5>3>6>4>7"

 

다른 결과는 2번 대신에 5번을 먼저 빼면, 그러면 큐에서 빠져나간 노드의 순서는 "1>5>2>3>6>4"

 

 

5. 구현 예시

 

진입차수 리스트 indegree를 만들어야한다.

 

방향그래프에서 a에서 b로 가는 간선이 존재하는것은, 결국 b의 진입차수가 1 증가한다는 말과 같다.

 

그리고 초기에 큐에 진입차수가 0인 노드들을 모두 넣어주고, 하나씩 빼면서 반복문을 수행하는데

 

큐에서 원소를 뺀 순서가 위상 정렬 결과이므로, 그것을 result에 담아줘야하고,

 

현재 뺀 노드 now와 연결된 정점 i를 조사해서 now에서 출발하는 간선을 제거한다는 것은

 

i의 진입차수를 1 감소시킨다는 말과 같다.

 

 

#위상정렬 알고리즘

from collections import deque

#노드의 개수와 간선의 개수

v,e = map(int,input().split())

#모든 노드에 대한 진입차수를 0으로 초기화함
#노드 번호는 1번부터 v번까지

indegree = [0]*(v+1)

#각 노드에 연결된 간선의 정보를 담는 연결리스트(그래프) 초기화

graph = [[] for _ in range(v+1)]

#방향 그래프의 모든 간선의 정보를 입력

for _ in range(e):
    
    a,b = map(int,input().split())

    graph[a].append(b) #정점 a에서 b로 이동가능하다

    #a에서 b로 이동하므로, b로 들어오는 간선의 개수가 1개 늘어났다.
    #b의 진입차수를 1 증가
    indegree[b] += 1

#위상 정렬 알고리즘
    
result = [] #알고리즘 수행 결과

q = deque() #deque로 삽입,삭제 빠르게

#처음 시작에는 진입차수가 0인 노드를 모두 큐에 넣는다.

for i in range(1,v+1):
    
    if indegree[i] == 0:
        
        q.append(i)


#큐가 빌 때까지
#큐에 노드 1개 꺼내고, 출발하는 간선 모두 제거하고, 새롭게 진입차수가 0인 노드를 큐에 넣고

#큐가 빌때까지 반복
while q:
    
    #큐에서 노드 1개 꺼내기
    now = q.popleft()

    #위상정렬 결과를 기록하기 위해
    result.append(now)
    
    #now와 연결된 정점을 모두 찾는다.
    for i in graph[now]:
        
        #now에서 출발하는 간선을 제거
        #now에서 i로 가는 간선을 하나 제거한다는 것은, 
        #i의 진입차수를 1 감소시킨다는 소리이다.

        indegree[i] -= 1

        #만약 진입차수가 0이 된다면... 큐에 i번 노드를 삽입한다
        if indegree[i] == 0:
            
            q.append(i)


#위상 정렬 결과

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

 

6. 시간복잡도

 

O(V+E)

 

차례대로 모든 노드 V개를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해야 한다. 간선을 모두 확인한다는 측면에서 O(V+E)가 된다.