위상 정렬

---

목차

---

📍 정의 및 특징

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

- 어떤 노드를 선택했느냐에 따라 결과가 달라지므로, 항상 같은 결과 보장 X

- 시간 복잡도 : O(V + E)

 

#사이클X  #방향그래프

 

📍 필요 변수

✔ 그래프 데이터 인접 리스트 (ArrayList<Node>[])

✔ 진입 차수 배열 (int[] D)

✔ 진입 차수가 0인 노드 저장할 큐 (= 정렬 배열)

 

 

📍 실행 과정

1. 그래프 데이터 인접 리스트 ArrayList<Node>[] & 진입 차수 배열 int[] D 초기화
    (예 : D[2]++ : 자기 자신을 가리키는 에지 개수)
   
   
2. 진입 차수 배열에서 진입 차수가 0인 노드를 큐(=정렬 배열)에 저장하고,
   선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼기
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer하기
   
   
4. 모든 노드 정렬될 때까지 (= 큐가 빌 때까지) 과정 1~3 반복

 

 

➕ 예제

[백준/JAVA] 2252번: 줄 세우기

[백준/JAVA] 1516번: 게임 개발