위상 정렬

[Algorithm/Python] 위상 정렬(Topology Sort)란?

들어가며본 포스팅에서는 위상 정렬에 대해 소개합니다.📌 위상 정렬이란?위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다. 1️⃣ 진입차수가 0인 노드를 큐에 담습니다. 2️⃣ 큐가 비어있을 때까지 다음의 과정을 반복합니다. - 1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다. - 2 ) 진입차수가 0인 노드를 큐에 담습니다. 모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다. 큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다. 1. 진입차수가 0인 노드 1을 큐에..