algorithm
[알고리즘] 위상 정렬(topology sort)
1. 위상 정렬이란 사이클이 없는 방향 그래프에서 노드간의 순서를 찾는 알고리즘이다. 순서가 정해져 있는 작업을 차례로 수행할 때, 그 순서를 결정하기 위해 사용하는 알고리즘이다. 사이클이 존재하면 노드간의 순서를 명확히 할 수 없기 때문에 위상 정렬을 적용할 수 없다. 늘 같은 정렬 결과를 보장하지 않는다. 2. 위상 정렬의 흐름 진입 차수(in-degree) : 자기 자신을 가리키는 간선의 개수 위와 같은 그래프가 주어졌을 때, 1) 진입 차수 배열을 생성한다. * 여기서 보면 노드1의 경우 0, 2와 3의 경우 1,4와 5의 경우 2가 된다. 2) 진입 차수 배열에서 값이 0인 노드를 큐에 저장한다. 3) 큐에서 poll한 노드를 결과 리스트에 추가하고, poll한 노드가 가리키는 노드들의 진입 차..
