Topological sorting1 [Java] 위상정렬 위상 정렬은 특정 수강과목에서 선수과목이 있을 경우 어떤 순서로 들어야 하는지 순서를 쉽게 찾아낼 수 있는 알고리즘입니다. 이때, 위상 정렬을 위해서는 그래프는 방향이 있어야 하고 사이클이 없는 DAG(Directed Acyclic Graph) 여야만 합니다. 위상 정렬 방법(Queue 사용) 1. 진입 차수 즉, 특정 노드로 들어오는 간선의 개수를 알아내기 위해 in 배열의 크기를 정점의 개수만큼 만듭니다. 2. 특정 노드로 들어오는 간선이 있을 때마다 in 배열의 크기를 +1 해줍니다. ex) 예를 들어, 위 이미지와 같은 DAG가 있다면 진입 차수는 1 2 3 4 진입 차수 0 1 0 3 와 같이 됩니다. 3. 큐를 만들고 진입 차수가 0인 노드를 전부 큐에 삽입합니다. 4. 큐에 아무것도 남지 않.. 2021. 5. 11. 이전 1 다음
