[Algorithm]Topology Sort(위상정렬)

참고 : https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

위상정렬(Topology Sort)

: 위상 정렬이란, 부분적인 요소들에 대하여 ‘이행되어야 할 순서가 정해져 있을 때’ 전체 요소들에 대하여 이행되어야 할 순서를 정해주기 위해 사용되는 알고리즘이다. 

 

위상정렬은 DAG(directed acyclic graph)에만 적용이 가능하다. 즉, 사이클이 발생하지 않아야 한다는 의미이다. 

사이클 발생의 여부는 위상정렬을 수행할 때, 모든 노드들을 돌기 이전에 q.empty()가 발생하느냐의 유무로 알 수 있다. 큐가 비게되면 사이클이 형성되어있다는 의미이다. 

 

따라서 위상정렬 알고리즘은 두가지의 결과를 제시한다.  

1. 현재 그래프는 위상 정렬이 가능한지(사이클이 존재하지 않는지)

2. 위상정렬이 가능하다면 그 결과는 무엇인지.

 

<위상정렬 방법> 1. 진입차수가 0인 정점을 큐에 삽입합니다.  2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.  3.간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입합니다.  4.큐가 빌 때까지 2번~3번 과정을 반복합니다. 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의결과입니다. 1>>2>>5>>3>>4>>6>>7