크롱의 Dev Log

선수 과목 체계 등 선행 관계가 있는 자료구조를 정렬할 때 필요한 알고리즘이 바로 위상정렬(topological sort)이다. 방향이 있는 그래프(단, 사이클이 없어야 함) 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 알고리즘이다. 유향 그래프(방향이 있는 그래프)에서 에지 가 있다면 정점u가 정점v를 선행한다.  위상 정렬 방법 ① 진입 차수(내차수)가 0인 임의의 정점 (선행자가 없는 정점) 출력 ② 출력한 정점에 부착된 모든 에지들을 제거하여 진입 차수 재계산 ③ 모든 정점이 제거될 때까지 ①~② 반복 ④ 진입 차수가 0인 것이 없으면, 그래프가 사이클을 포함한 것으로서 해가 존재하지 않음.  위상 정렬 알고리즘 (C언어) 아래와 같은 입력 형식의 사이클이 없는 방향그..