[파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란?

위상 정렬(Topology Sort)은 순서가 정해져 있는 작업을 수행해야 할 때 사용하는 사용할 수 있는 알고리즘입니다.

 

대학교 수강 과목 리스트를 예로 나타내 볼게요! 저는 컴퓨터공학과 학생이기 때문에 저의 수강 리스트를 위상 정렬로 예를 들면 위와 같이 나타낼 수 있습니다. 자료구조와 컴퓨터구조 수업을 수강하기 위해서는 프로그래밍 실습수업을 선수강해야 하고 알고리즘 수업을 수강하기 위해서는 자료구조 수업을 선수강해야 합니다. 이 과목들을 모두 수강한 후에야 비로소 최종적으로 운영체제 수업을 수강할 수 있습니다. 

 

기억나는 대로 그냥 예시로 든 것이니 실제 선수 과목과 다를지라도 그냥 넘어가 주시면 감사하겠습니다.ㅋㅋㅋㅋ

 

---

위상 정렬의 특징

 

1) 위상 정렬에서는 여러 개의 답이 존재할 수 있음

위와 같이

 

프로그래밍 실습 -> 자료구조 -> 알고리즘 -> 컴퓨터구조 -> 운영체제

 

이 순서로 나타낼 수도 있고

 

프로그래밍 실습 -> 자료구조 -> 컴퓨터구조  -> 알고리즘 -> 운영체제

프로그래밍 실습 -> 컴퓨터구조 -> 자료구조 -> 알고리즘  -> 운영체제

 

이렇게 나타낼 수도 있습니다.

 

2) 위상 정렬은 DAG일 때만 적용 가능

 

DAG란 Directed Acyclic Graph의 줄임말로써 방향 그래프 중 사이클이 존재하지 않는 그래프를 의미합니다. 

 

위와 같이 그래프가 사이클이 존재하게 된다면 시작 지점을 정할 수가 없기 때문에 순서를 정할 수가 없습니다. 

 

---

위상 정렬의 동작 과정

위상 정렬은 큐를 사용하여 구할 수 있습니다.

 

2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

[파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue)

1. *진입 차수가 0인 노드를 큐에 삽입
2. 큐에서 노드를 꺼내면서 해당 노드와 연결된 노드의 간선을 제거
3. 이후 간선이 제거되어 진입 차수가 0이 된 노드를 큐에 삽입
4. 2~3 반복

*진입 차수= 노드로 들어오는 간선의 개수

 

1) 각 노드의 진입 차수를 담은 테이블과 큐를 준비.

 

2) 진입 차수가 0인 노드 1을 큐에 삽입.

 

3) 큐에서 노드 1을 꺼내면서 노드 1과 연결되어 있는 간선을 모두 제거. 노드 1과 연결되어 있던 노드 2와 4의 진입 차수는 1씩 감소.

 

4) 노드 2와 4의 진입 차수가 0이기 때문에 큐에 삽입.

 

5) 큐에서 노드 2를 꺼내면서 노드 2과 연결되어 있는 간선을 모두 제거. 노드 2과 연결되어 있던 노드 3의 진입 차수는 1 감소.

 

6) 노드 3의 진입 차수가 0이기 때문에 큐에 삽입.

 

7) 큐에서 노드 4를 꺼내면서 노드 4와 연결되어 있는 간선을 모두 제거. 노드 4와 연결되어 있던 노드 5의 진입 차수는 1 감소.

 

8) 큐에서 노드 3을 꺼내면서 노드 3과 연결되어 있는 간선을 모두 제거. 노드 3과 연결되어 있던 노드 5의 진입 차수는 1 감소.

 

9) 노드 5의 진입 차수가 0이기 때문에 큐에 삽입.

 

10) 큐에서 노드 5 꺼냄

 

꺼낸 순서: 1 -> 2 -> 4 -> 3 -> 5

 

---

위상 정렬 구현

코드

from collections import deque

def topology():
    dQ=deque()
    
    # 진입차수가 0인 노드들 큐에 삽입
    for i in range(1, NODE_CNT+1):
        if degree[i]==0:
            dQ.append(i)
            
    print('###############')
    print('Topology Sort')
    while dQ:
        v=dQ.popleft()
        print(v, end=' ')
        # 큐에서 노드 꺼내면서 연결된 노드의 진입차수 1씩 감소
        for i in range(1, NODE_CNT+1):
            if graph[v][i]==1:
                degree[i]-=1
                # 진입차수가 0이면 큐에 삽입
                if degree[i]==0:
                    dQ.append(i)
    print()
    print('###############')
    
if __name__ == "__main__":
    NODE_CNT = 5
    graph=[[0]*(NODE_CNT+1) for _ in range(NODE_CNT+1)]
    degree=[0]*(NODE_CNT+1)
    
    graph[1][2] = 1
    degree[2] += 1
    graph[1][4] = 1
    degree[4] += 1
    graph[2][3] = 1
    degree[3] += 1
    graph[3][5] = 1
    degree[5] += 1
    graph[4][5] = 1
    degree[5] += 1

    topology()

결과

모든 노드를 확인하면서 확인하는 노드와 연결된 간선을 제거해야 되기 때문에 O(V) + O(E) = O(V + E) (V는 노드의 개수, E는 간선의 개수)의 시간 복잡도를 갖습니다.