위상 정렬 (Topology sort)

토폴로지(영어: topology, 문화어: 망구성방식)는 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것, 또는 그 연결 방식을 말한다.

 

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

25. 위상 정렬(Topology Sort)

(위 안경잡이개발자 님의 블로그를 보고 공부했습니다.) 

 

 

 

위상정렬은 순서가 정해져있는 작업을 순서대로 수행할때 그 순서를 결정해준다.

위상정렬은 서로다른 두 일이 우선순위를 갖고있을때 전체적인 순서를 정해준다. 이 우선순위는 모든 일들에 대하여 주어지지 않을수 있으므로 위상정렬 결과는 여러가지가 나올수 있다. 

 

위상정렬의 조건

위상정렬은 사이클이 발생하지 않는 방향 그래프에서만 가능하다. (시작점이 존재해야한다!) 

 

 

위상정렬 알고리즘의 작동은 다음과 같다

 

1. 모든 노드들의 진입차수를 계산한다. (진입차수란 노드에 진입하는 간선의 갯수다) 

 

2. 진입차수가 0인 노드들을 큐에 푸쉬한다. (시작점) 

 

3. 큐에서 노드를 꺼내면서 꺼낸 노드와 연결된 노드들의 진입차수를 감소시킨다. 감소시킨 결과 0이 되면 (해당 노드에 진입하는 간선이 모두 사라졌다면) 큐에 삽입한다.

 

2-3 반복한다 

 

4. 큐에서 꺼낸 노드의 순서가 위상정렬의 결과다. 

 

 

 

 

위상정렬을 이용한 문제 

https://tose33.tistory.com/617