그래프

08-3 위상 정렬

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에선 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

인접 리스트 -> 두 노드간의 위상 관계를 저장
진입 차수 리스트 -> 자기 노드까지 오기 위해 거쳐야 하는 노드 수를 저장(0이 되면 자기 차례)

진입 차수가 0인 노드를 큐에 넣고 넣은 노드가 가리키는 노드의 진입 차수를 모두 1씩 감소 -> 큐가 빌때까지 반복