[알고리즘] - 위상정렬

 

Topology Sort

---

정렬 알고리즘의 일종인 위상정렬 알고리즘은 '순서가 정해져 있는 일련의 작업을 수행할때' 사용하는 알고리즘이다. 즉 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것을 위상정렬이라고 한다. 

예를들면 선수과목을 생각하면 편하다. B라는 과목을 듣기 위해서 A라는 과목을 필수로 들어야 한다는 것과 동일하다. 즉 순서가 정해져있는 일련의 작업을 의미하게 된다. 

 

 

Toplogy Sort Algorithm

---

위상정렬 알고리즘은 다음 순서로 동작한다.

 - 진입차수가 0인 노드를 큐에 넣음

 - 큐가 빌때까지 다음 과정을 반복

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

 - 새롭게 진입차수가 0이 된 노드를 큐에 넣음

 

만약 이 과정에서 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다는 의미가 된다.

 

 

from collections import deque

def topology_sort():
    # 수행 결과를 담을 리스트
    result =[]
    q = deque()

    # 처음 시작할 때 진입차수가 0인 노드를 큐에 삽입
    for i in range(1,v+1):
        if indegree[i]==0:
            q.append(i)
    # 빌 때까지 반복
    while q:
        idx = q.popleft()
        result.append(idx)
        for i in graph[idx]:
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)

    # 위상 정렬 수행 결과 출력
    for i in result:
        print(i,end=" ")


# 노드 간선의 개수
v,e = map(int,input().split())

# 그래프 정보 리스트와 진입차수 리스트
graph=[[] for i in range(v+1)]
indegree = [0]*(v+1)

# 간선 정보 입력
for _ in range(e):
    a,b = map(int,input().split())
    graph[a].append(b)
    indegree[b]+=1

topology_sort()

 

Reference

---

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

https://backtony.github.io/algorithm/2020-09-09-algorithm-basics-coding-11/

그래프 이론 with 파이썬

https://katfun.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0

그래프 이론

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?