위상정렬 알고리즘

위상정렬(Topology Sort) ?

• 위상정렬 알고리즘은 사이클이 없는 그래프에서 노드의 순서를 찾는 정렬 알고리즘이다.
• 그래프 내의 노드들 간의 선후 관계를 결정하여, 어떤 작업들이 먼저 수행되어야 하는지 순서를 정하는 것이 목표이다. → 작업의 선후 관계를 결정해야 하거나 특정 순서로 작업을 처리해야 하는 문제에서 사용된다 !

💡 위상정렬 핵심 개념 - 유향 비순환 그래프(DAG)

• 위상정렬은 반드시 사이클이 없는 유향 그래프에서만 적용 가능하다 ! → 그 이유는 당연하게도 사이클이 있다면, 노드 간의 선행 관계를 정의할 수 없기 떄문에 !

<aside> 💡

선행 관계 ?

• 간선(u → v)이 있을 때, u는 항상 v보다 앞에 와야 한다는 의미이다. </aside>

💡 위상정렬 핵심 개념 - 진입 차수(In-degree)

• 진입 차수는 특정 노드로 들어오는 간선의 개수를 의미한다.
• 진입 차수가 0인 노드는 현재 해당 노드 이전에 처리해야 할 노드가 없다는 것을 의미 ! ****→ 위상정렬 과정에서 진입 차수가 0인 노드를 처리하며 간선을 제거한다.