[그래프] 위상정렬

위상정렬

사이클이 없는 방향에서 노드 순서를 갖는 정렬

기능	특징	시간복잡도 (노드수: V, 엣지수: E)
노드간 순서 결정	사이클이 없어야 함	O(V+E)

 

• 항상 유일한 값으로 정렬되지 않음
• 사이클 존재시 노드간 순서를 명확하게 정의 불가 (위상정렬 적용 불가)

 

핵심 이론

인접리스트 , 진입차수배열 , 위상정렬배열 세가지를 구현한다.

 

1. 그래프를 인접리스트로 구현

2. 구현된 인접리스트의 진입차수를 계산하여 진입차수 배열에 저장

3. 진입차수배열에서 진입차수가 0인 노드 선택

4. 선택된 노드 위상정렬 배열에 저장

5. 저장된 노드가 가리키는 노드들의 진입차수를 -1 연산 후 저장(선택) 된 노드의 다음노드를 진입차수 배열에서 다시 선택

6. 3 ~ 5 과정을 반복하며 모든 노드가 정렬될 경우 종료

---

[그래프]

① → ② → ⑤  ↓      ↓  ↗ ③ → ④

 

①②③④⑤

①②③④⑤

①②③④⑤

 

Step 01) 진입 차수 배열을 초기화

#01) 인접 리스트 ArrayList<Node> [N]를 구현한다.

ArrayList<Node> [N]

① → ② ③

② → ④ ⑤

③ → ④

④ → ⑤

⑤

#02) 진입 차수를 계산

진입차수란?

자기 자신을 가리키는 엣지의 갯수

ArrayList<Node> [N]	진입차수
① → ② ③	D[2]++ D[3]++
② → ④ ⑤	D[4]++ D[5]++
③ → ④	D[4]++
④ → ⑤	D[5]++
⑤

 

#03) 계산된 진입차수를 토대로 진입차수배열 초기화

노드	1	2	3	4	5
진입차수	0	1	1	2	2

 

Step 02) 진입 차수 0인 노드 선택 → 정렬배열 저장 → 저장한 노드가 가리키는 노드 진입차수 -1

#01) 진입차수 배열에서 진입 차수가 0인 노드 선택

노드	1	2	3	4	5
진입차수	0	1	1	2	2

위 진입차수 배열에서 진입차수가 0인 노드는 1이므로 노드 1을 선택한다.

 

#02) 선택한 노드 정렬 배열에 저장

정렬배열

1

진입차수가 0인 선택된 노드 1을 정렬 배열에 저장

 

#03) 저장된 노드가 가리키는 모든 노드의 진입차수 -1

노드	1	2	3	4	5
진입차수	0	1 ↓ 0	1 ↓ 0	2	2

저장된 노드 1이 가리키는 노드는 2와 3이므로 각 노드의 진입차수를 -1 연산한다.

 

#04) 01 ~ 02 작업을 반복하며 모든 노드 정렬시 종료된다.

 

case 01 : 2와 3중 2 선택

2는 4와 5를 가리키므로 노드 4와 5의 진입차수를 각각 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	2 ↓ 1	2 ↓ 1

 

3 선택 -  3은 4를 가리키므로 노드4의 진입차수를 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	1↓ 0	1

 

4 선택 - 4는 5를 가리키므로 노드 5의 진입차수 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	0	1 ↓ 0

 

case 02 : 2와 3중 3 선택

 

3 선택 -  3은 4를 가리키므로 노드4의 진입차수를 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	2 ↓ 1	2

 

2는 4와 5를 가리키므로 노드 4와 5의 진입차수를 각각 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	1↓ 0	2↓ 1

 

4 선택 - 4는 5를 가리키므로 노드 5의 진입차수 -1 연산

노드	1	2	3	4	5
진입차수	0	0	0	0	1 ↓ 0

 

인접 리스트와 진입배열에서의 마지막 노드인 5까지 정렬 했으므로 정렬을 종료한다.

 

2가지 정렬 결과

정렬결과 1	1	2	3	4	5
정렬결과 2	1	3	2	4	5

 

타 그래프와 차이점

진입 차수(in degree) 배열을 기준으로 그래프 알고리즘이 적용된다.