위상 정렬
사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
진입차수 Indegree
특정한 노드로 들어오는 간선의 개수
진출차수 Outdegree
특정한 노드에서 나가는 간선의 개수
큐를 이용하는 위상 정렬 알고리즘의 동작 과정
집입차수가 0인 모든 노드를 큐에 넣는다
큐가 빌 때까지 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
새롭게 진입차수가 0이된 노드를 큐에 넣는다
위상 정렬은 DAG 순환하지 않는 방향 그래프에서만 수행 가능
한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상이면 여러가지 답이 존재 가능
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 가능
스택을 활용하여 DFS를 활용해 위상 정렬 가능
