위상정렬 (topological sorting)

위상정렬

 

위상정렬이란 위키나무 에서 다음과 같이 정의한다. 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다. 일반적인 위상 정렬의 적용은 주로 업무의 일정을 일어나야 할 순서에 따라 배치하기 위하는 것으로, 이 알고리즘은 프로젝트 관리 기법을 평가 및 분석하기 위한 기법(PERT)에 적용하기 위한 목적을 위해 1960년대 초반부터 연구되었다 (Jarnagin 1960). 이 때, 해당 업무는 꼭짓점으로 표현되었고, 각 꼭짓점을 연결하는 변은 해당 업무 간의 선후 관계를 표현하였다. 가령, 옷을 다리기 위한 업무는 반드시 옷을 세탁기에 돌리는 업무 뒤에 배치되어야 한다. 이와 같이, 위상정렬은 각 업무를 수행하기 위한 순서를 제공하였다. Topological sorting(위상 정렬)은 컴퓨터 과학에서, 방향 그래프의 위상 정렬 또는 위상 배치는 정점의 선형 순서이다. 꼭짓점 u에서 꼭짓점 v로의 모든 방향 꼭짓점 uv는 v의 순서 전에 u가 오는 것이다. 예를 들어, 그래프의 꼭짓점은 아마 수행하는 일은 대표한다. 그리고 꼭짓점은 어떤 일이 다른 것보다 먼저 수행되어야 하는 허가되지 않은 것을 대표한다. 이러한 것에서, 위상 배열은 일의 유용한 순서에 불과하다. 정확히 위상 정렬은 모든 종속성을 방문한 후에만 각 노드 v를 방문하는 그래프 순환이다. 위상 배열은 가능하다. 정말 만약에 그래프 방향이 없는 순환이라면, 아마 그것은 방향 순환 그래프(DAG)일 것이다. 어떤 DAG는 최소 하나의 위상 배열을 가지고 있다. 그리고 알고리즘은 어떤 DAG 속 선형 시간의 위상 배열이 구성한다고 알려져 있다. 위상 정렬은 feedback arc set 와 같은 랭킹 문제를 해결하는데 많이 사용된다. 위상 정렬은 심지어 DAG의 요소가 연결되지 않을지라도 가능하다.

 

내가 이해한 바로 쉽게 말하면 메이플 같은 느낌이다

 

메이플 3차 스킬은 1차 스킬을 배우고 2차스킬을 배우고 난 후에 배울 수 있다.

1차스킬만 배웠다고 해서 배울 수 없고, 2차 스킬만 배웠다고 배울 수 없다.

 

위상정렬에서는 진입차수와 진출차수가 있다

두 개가 뭐냐면  진입차수 특정한 노드로 들어오는 간선의 개수  진출차수는 특정한 노드로 나아가는 간선의 개수이다.

 

1차 스킬은 진출차수 가 2, 진입차수 0 이고

2차는 진입1 진출 1

3차는 진입 2 인 것이다.

 

진입차수가 0 인 노드를 먼저 큐에 집어넣어 해당 노드에서 나아가는 간선을 제거 해주고

그러면서 -1 씩 바뀐 진입차수중에 0이 된 노드들을 큐에 넣어주어 큐가 빌때 까지 진행해주면 된다.

 

그래서 보통 우선순위큐를 사용한다.

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

import heapq
n, m = map(int, input().split())
array = [[] for i in range(n+1)]
indegree = [0] * (n+1)
heap = []
res = []

# 진출차수 만들어 줌
for _ in range(m):
    x,y = map(int,sys.stdin.readline().split())
    array[x].append(y)
    indegree[y] += 1
# 진출 차수 0인 노드 heapq 에 추가
for i in range(1,n+1):
    if indegree[i] == 0:
        heapq.heappush(heap,i)
위상정렬 진행 
while heap:
    num = heapq.heappop(heap)
    res.append(num)
    for i in array[num]:
        indegree[i] -= 1
        if indegree[i] == 0:
            heapq.heappush(heap,i)

for i in res:
    print(i, end=" ")