목록위상정렬 (1)

Binary Journey

[Algorithm] Topology Sort (위상 정렬)

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 떄 순서를 결정해주는 알고리즘이다. 위상정렬은 여러 개의 답이 존재할 수도 있고 사이클이 발생하는 경우 수행이 불가능하다는 특징이 있다. 위상 정렬 수행으로는 스택과 큐를 사용하는 데 큐로 더 고급적인 수행이 가능하다고 인강에선 큐를 이용하여 소스를 작성하였다. 순서로는 진입차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내어 연결된 모든 간선 제거 간선 제거 이후 진입차수가 0이 되는 정점을 큐에 삽입 큐가 빌 때까지 2,3번 과정 반복 - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 것 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과임 위 그림을 표로 나타내면 정점 1 2 3 4 5 6 7 진입차수 0 1 1 1 1 2..
Algorithm/알고리즘 스터디(2021.07) 2021. 10. 17. 22:13
이전 Prev 1 Next 다음