[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란?

 

위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방문해야 현재 노드에 방문할 수 있습니다. 위상 정렬 알고리즘은 선행 노드가 무조건 수행되어야 하기 때문에 사이클이 발생하지 않습니다.

 

 

2. 위상 정렬 알고리즘(Topological Sort Algorithm) 동작 원리?

 

위상 정렬이란 선행 노드가 수행이 되었을 때, 즉 진입 차수가 0일 때 현재 노드를 방문할 수 있습니다.

 

 

위 그래프의 진입 차수는 다음과 같습니다.

 

 

이때 진입 차수가 0인 노드들을 queue에 넣어줍니다.

 

queue

 

queue에서 숫자를 하나씩 빼주면서 연결되어 있는 노드의 진입 차수를 하나씩 빼주면서 진입 차수가 0이 되면 queue에 넣어줍니다.

 

queue

위상 순서

위와 같은 방법으로 반복해줍니다.

queue

위상 순서

 

queue

위상 순서

 

queue

위상 순서

 

queue

위상 순서

 

위상 순서

 

위상 정렬을 이용하여 다음 문제들을 풀 수 있습니다.

https://rudalsd.tistory.com/73?category=1064612 

[ 백준 ] 1948번 - 임계경로 (C++)