위상 정렬

Directed Acyclic Graph (DAG)

• 간선에 방향성이 있다
• 사이클이 없다
• 그래프 = 정점 + 간선
• Degree 차수 란 ? 정점에 연결되는 간선의 개수
• 방향성 그래프에서 차수는 inDegree와 outdegree로 구별
• inDegree 자신에게 들어오는 차수 / outDegree 자신에서 나가는 차수

정점들을 위상에 맞춰 정렬

InDegree가 없는 정점 먼저

사이클이 존재한다면 정렬 할 수 없음

아이디어

Q. “제일 먼저” 올 수 있는 정점은 ?

---

A. “들어오는 간선”이 없는 정점!

1. 제일 먼저 올 수 있는 정점들의 후보들을 담아 둠
   1. 어떤 자료구조에 담을 지는 나중에 생각
2. 그 후보 중 아무거나 하나 골라서 정렬하고 그래프에서는 삭제 해 줌
3. 삭제해주면서 간선들도 사라짐
4. 남은 그래프에서 inDegree 가 없어진 정점을 자료구조에 담음
5. 반복

모든 정점의 InDegree를 계산 먼저 해줌

그후 정점을 찾아서 자료구조 D에 넣고

D가 빌때까지 InDegree 가 0인것을 D에 추가하고 제거하는 것을 반복

자료구조 D가 하는 일

• 원소를 추가하기
• 원소를 꺼내기

→ 이걸 빠르게 해주는 것은 ?? Queue,Stack,Linked List (넣고 빼는건 O(1) )

while queue:
	x = queue.pop()
	for y in adj[x] :
		indeg[y] -= 1
		if indeg[y] == 0 :
			queue.append(y)

시간 복잡도를 낮게 하기 위해 D가 빌때까지 X를 꺼내서 정렬시키고 제거하는 것을

새롭게 정렬 가능한 점을 찾아서 D에 넣는다. (모든 간선을 다 탐색할 때 보다 훨씬 빨라짐)

→ O(|E|)