알고리즘 코딩테스트 핵심이론 강의 - 위상정렬

https://www.youtube.com/watch?v=caRfN1Xkw88

📌 위상정렬

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
  → 사이클이 존재하면 안됨
• 항상 유일한 값으로 정렬되지 않는다.

기능특징시간 복잡도(노드수 : V , 에지 수 : E)

노드 간의 순서를 결정

사이클이 없어야 함

O(V+E)

 

◾ 위상 정렬의 원리

출처 : https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

• 진입차수 : 자기 자신을 가리키는 에지의 개수

1. 진입차수 배열 생성

2. 진입차수 내열에서 차수가 0인 노드 선택 후 선택 된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺌

• 사용한 노드는 빼고 다시 진입차수가 0번째 노드를 넣고...반복
• 진입차수 배열을 기준으로 그래프 알고리즘이 돌아간다.