[알고리즘 파이썬] 위상 정렬

그래프 알고리즘 중 하나인 위상 정렬은 BFS, DFS보다 효율적일 수 있다.

 

의미 : 순서가 정해져있는 작업를 수행할 때 사용하는 알고리즘 

위상 정렬의 조건

주어진 그래프에서 위상 정렬을 하려면, 아래와 같은 조건을 만족하는 그래프여야 한다. 

1. 위상 정렬을 할 그래프는 간선이 방향을 가지는(유향) 그래프여야 한다.
2. 내부에 순환(cycle)이 있으면 안된다.

큐(Queue)를 이용한 방식

주어진 그래프에서 위상 정렬을 하려면, 아래와 같은 조건을 만족하는 그래프여야 한다.

1. 진입차수가 0인 정점을 큐에 삽입한다. (들어오는 연결선이 없는 노드)
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
3. 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.
4. 2번, 3번 반복