목록toplogy sort (1)

맞왜틀

위상 정렬(topology sort)

📔 위상 정렬(topology sort) 이란 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 어떤 일을 하는 순서를 찾는 알고리즘 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 선행 조건이 반드시 수행되어야 다음을 진행할 수 있다! 위의 그림을 보면 아비터트리뷰널을 짓기 위해서는 템플러아카이브와 스타게이트가 둘다 있어야 한다. 시간복잡도: O(V+E) | V-노드의 수, E-간선의 수 📔 위상 정렬(topology sort) 구현 큐와 스택을 사용할 수 있다. 일반적으로 큐를 사용 진입 차수( 현재 노드에 들어올 수 있는 노드의 수 ) 가 0인 정점을 큐에 삽입 (그림의 사이버네틱스코어) 큐에서 원소를 꺼내 연결..
CS/Algorithm 2020. 10. 5. 20:05
이전 Prev 1 Next 다음