JUINTINATION

위상정렬(Topological Sort)이란? 유향 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 다음 라면 끓이기 예제를 보자 우리는 라면을 끓일 때 냄비에 물을 먼저 부어도 되고 라면 봉지를 먼저 뜯어도 되지만 계란은 맨 마지막에 풀어야 한다. 이러한 방향은 있지만 사이클은 없는 그래프를 간선의 방향을 거스르지 않고 한 줄로 정렬시키는 것이 위상정렬이라고 보면 될 것 같다. 위상정렬 알고리즘(1) 진입 간선이 없는 정점을 연결리스트 R의 맨 뒤에 연결하고 해당 정점과 그 정점의 진출 간선을 제거하는 과정을 반복한다. 의사 코드는 다음과 같으며 위의 예시를 구하는 과정은 그 다음 그림과 같다. topological_so..