[알고리즘] - 위상정렬

ALGORITHM/Algorithm 설명

[알고리즘] - 위상정렬

Hitree 2022. 3. 19. 19:49

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()