위상정렬

의미

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.

진입차수, 진출차수

• 진입차수 Indegree : 특정한 노드로 들어오는 간선의 개수
• 진출차수 Outdegree : 특정한 노드에서 나가는 간선의 개수

위상정렬 알고리즘

• 큐 이용

1. 진입차수가 0인 모든 노드를 큐에 넣음
2. 큐가 빌 때까지 다음 과정 반복
   a. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   b. 새롭게 진입 차수가 0이 된 노드를 큐에 넣음

• 각 노드가 큐에 들어온 순서 == 위상 정렬을 수행한 결과

특징

• DAG 에 대해서만 수행 가능
  • DAG (Direct Acyclic Graph) : 순환하지 않는 방향 그래프
• 여러 답이 존재할 수 있음.
• 모든 원소 방문 전에 큐가 비면 사이클이 존재
  • 사이클에 포함된 원소는 큐에 들어갈 수 없음
• 스택을 활용한 DFS로 위상 정렬 수행 가능

https://freedeveloper.tistory.com/390