위상 정렬 Topology Sort

위상 정렬 Topology Sort 

• 태스크 수행 순서를 찾는 알고리즘
• 방향 그래프에 존재하는 각 정점의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
• Directed Acyclic Graph에만 적용 가능 (사이클이 발생하지 않는 방향 그래프)
• 하나의 그래프에서 여러 개의 위상정렬이 도출될 수 있다.
• 위상정렬의 시작점이 있어야 한다.
• 그래프에 남아 있는 정점 중 진입차수가 0 인 정점(해당 정점으로 들어오는 간선이 없는 경우)이 없다면 위상정렬 알고리즘 종료
• example 

1. 진입 차수가 0 인 정점 (들어오는 간선의 수가 0, 위상 정렬의 시작점이 될 수 있는 정점)을 선택

   → 여러 개인 경우 아무거나 선택

   → 초기에 진입 간선의 수가 0 인 모든 정점을 큐에 삽입 : (0) (1)

2. 선택된 정점과 해당 정점에 연결된 간선을 삭제

   → 해당 정점을 큐에서 삭제하면서 위상 순서에 삽입 (0)

3. 위 과정을 반복하면서 모든 정점이 큐에서 제거되면 알고리즘 종료

• step by step 설명

  ** 여기서 선택된 정렬이란 큐의 head에 있는 정점을 의미

  • (0) (1) 을 큐에 삽입

  • 선택된 정점 (0)에 연결된 간선 모두 삭제하고 (0)을 위상순서에 삽입

    ** 현 위상 순서 상태: (0)

  • 진입 간선이 없는 (2) 를 큐에 삽입

  • 선택된 정점 (1)에 연결된 간선을 모두 삭제하고 (1)을 위상순서에 삽입

    ** 현 위상 순서 상태 (0) (1)

  • 진입간선이 없는 (4)를 큐에 삽입

  • 선택된 정점 (2)에 연결된 간선을 모두 삭제하고 (2)를 위상순서에 삽입

    ** 현 위상 순서 상태 (0) (1) (2)

  • 진입 간선이 없는 (3) 을 큐에 삽입

  • 선택된 정점인 (4)에 연결된 간선을 모두 삭제하고 (4)를 위상순서에 삽입

    ** 현 위상 순서 상태 (0) (1) (2) (4)

  • 진입간선이 없는 (5) 를 큐에 삽입

  • 선택된 정점 (3)에 연결된 간선을 모두 삭제하고 (3)을 위상순서에 삽입

    ** 현 위상 순서 상태 (0) (1) (2) (4) (3)

  • 남은 (5)를 위상순서에 삽입

    ** 현 위상 순서 상태 (0) (1) (2) (4) (3) (5)

---

References

• gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html