위상 정렬(Topology-sort)

목차

1. 위상 정렬이란?
2. 알고리즘 사용 예시
3. 불가능한 예시

1. 위상 정렬이란?

방향이 있는 유향 그래프의 정점들을 간선의 방향에 위배되지 않도록 나열한 것입니다.

2. 알고리즘 사용 예시

위 그래프를 예시로 위상 정렬의 과정을 설명하겠습니다.

우선 앞서 설명했던 큐와 위상 정렬을 저장할 배열을 준비합니다.
정점 중 진입 차수가 0인 정점을 큐에 저장합니다.
해당하는 정점이 여러 개가 있다면 전부 큐에 추가합니다.

위 예시에서는 정점 1이 큐에 추가되었습니다.
이후 선택된 정점과 연결된 간선을 그래프에서 지워버립니다.
큐에서 해당 정점을 지우고 정렬에 추가합니다.

이후 위 두 과정을 반복합니다.

3. 불가능한 예시

위 그래프는 앞서 보여드렸던 예시에서 간선 하나를 추가해 싸이클을 만들어 놓은 것입니다.
정점 1, 3, 6만으로 생각해 봅시다. 어떠한 정점으로 시작해도 간선의 방향에 위배됩니다.
이런 식으로 그래프에서 싸이클이 형성된다면 해당 그래프로는 위상 정렬이 불가능합니다.