그래프
-
[Algorithm] - 위상 정렬Algorithm/Algorithm 2022. 9. 1. 22:26
위상 정렬 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 싸이클이 존재하는 경우는 발생할 수 없다 일반적으로 방향그래프로 설정이 되어 있기 때문에 Indegree 값이 0인 Node들에서 먼저 시작하면서 VFS 처럼 구현하면 된다. 위상 정렬의 결과가 Node들의 수와 동일해야 한다! ( 동일하지 않는 경우는 Cycle이 발생된 경우 ) 알고리즘 시간 복잡도 : O( V+E ) 1. 처음 방향 그래프들의 Edge를 읽으며, Indegree Table을 설정 2. Indegree가 0인 Node들을 Queue에 넣는다. 3. Queue에 Node들을 꺼내며, 위상 정렬 값 추가 4. 연결된 Node들의 Indgree값을 줄여주고 , 0이면 Queue에 추가 5. 3~4..