⭐️위상 정렬이란?

위상 정렬(Topological Sort)은 방향 그래프(Directed Graph)에서 정점(Vertex)들을 일렬로 나열하는 알고리즘입니다. 이 때, 그래프의 방향은 항상 한쪽으로 향하며, 순환(Cycle)이 없어야 합니다.
위상 정렬은 그래프에서 선후 관계에 따라 정점들을 정렬하는 것으로, 여러 개의 정점들 간에 어떤 정점이 선행되어야 하는지를 나타냅니다. 이를 통해 작업의 선후 관계를 파악하거나, 의존 관계를 해결하기 위해 사용됩니다.
-chatGPT

위상 정렬을 이해하기에 앞서 위상 정렬을 그래프를 1차원 배열로 정렬하는 것이며 방향이 있는 directed graph에서 수행되며 해당 그래프는 cycle이 없어야 한다.

⭐️위상 정렬 알고리즘

위상 정렬 알고리즘에는 stack을 이용한 알고리즘과 queue를 이용한 알고리즘이 있다. 해당 게시글에서는 queue를 이용한 알고리즘을 설명하겠다.

1. 그래프의 모든 정점에 대해 방문하지 않은 정점을 선택하고 큐에 삽입한다.
2. 큐에서 노드를 꺼낸 후 연결된 모든 edge를 제거한다.
3. 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입한다.
4. 큐가 빌 때까지 2, 3번을 반복한다. 모든 원소를 방문하기 전에 3번을 수행한 이후에 큐가 비어있다면 해당 상황은 cycle이 있는 상황이므로 위상 정렬이 불가능하다.

🌈간선

노드와 노드를 연결하는 edge를 의미한다.

🌈정점

inDgree가 0인 노드를 의미한다. inDegree란 해당 노드로 들어온 edge의 갯수를 의미한다.

⭐️위상 정렬 예시

위 그래프는 directed graph이며 cycle이 존재하지 않는다. 즉, 위상 정렬이 가능한 그래프이다.

위상 정렬은 위에서 설명한 알고리즘대로 정점을 선택하고 큐에 삽입하며 큐에서 노드를 꺼내면서 edge를 제거하고 새로운 정점을 큐에 넣는 것이 반복된다.

result queue를 순서대로 빼내면 빼는 순서가 바로 위상 정렬된 결과이다.