[서울대학교 논자시 준비] 알고리즘 : chapter 10 그래프 : 위상정렬

위상 정렬은 2022년도 1학기 서울대학교 석사 시험에 나왔던 문제이다. 노드 i와 j 사이에 간선 (i, j)가 존재한다면 노드 i는 노드j보다 먼저 수행되어야한다. 모든 간선에 대해서 이 성질만 만족시킨다면 노드 간의 어떤 순서라도 좋다. 이런 성질을 만족하는 정렬을 위상 정렬, topological sort이라고 한다. 간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야한다 만약 그래프에 사이클이 있다면 이 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다. 동작 방식은 아래와 같다. 알고리즘 1. topologicalSort(G, v){ for i

2023.08.26