C#으로 위상정렬(Topological Sort) 구현하기

안녕하세요. 이번 포스팅에서는 위상정렬에 대해서 알아보겠습니다. 먼저 위상정렬이란? 순서가 정해져 있는 일련의 작업들을 차례대로 수행할 때 사용합니다. 사이클이 없는 방향 그래프의 모든 노드를 방향성에 위배되지 않도록 순서대로 나열하는 것입니다. 위상 정렬의 특징은 사이클이 없는 방향 그래프(DAG : Direct Acyclic Graph)에 대해서만 수행할 수 있습니다. 위상정렬로 정렬을 하면 답이 여러가지로 나올 수 있습니다. 하나의 방향 그래프에는 여러가지의 위상 정렬이 가능합니다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라고 한다. 모든 원소를 방문하기 전에 큐가 비어버리게 된다면 사이클이 존재한다고 판단할 수 있습니다. 참고로 위상정렬을 찾으시는 분들 중에 Kahn의 알고리즘이랑 헷갈리시는 분들이 있는데 Kahn의 알고리즘은 위상정렬 알고리즘 중 하나이지 Kahn이 위상정렬인것은 아닙니다. 구현 방법으로는 in_degree를 ...

원문링크 : C#으로 위상정렬(Topological Sort) 구현하기