[graph]위상정렬

위상 정렬이란?

DAG(Directed Acyclic Graph), 즉 방향 사이클이 없는 방향그래프에서 노드들의 순서화를 진행하는 것을 말한다. 즉 노드들간의 순서를 정렬한다는 의미이다.

위상정렬 알고리즘

첫번째

TopologicalSort(G) {

for 1 to n{

indegree가 0인 임의의 정점 u를 선택

A[i] <- u;

정점 u와 u의 진출 간선을 모두 제거한다.

}

배열 A[1...n]에는 정점들이 위상정렬 되어있음.

}

두번째

TopologicalSort(G) {

for each v in V 

visited[v] <- no

비어있는 linked list R을 생성한다.

for each v in V

if (visited[v]==no) then

dfs-ts(v,R);

}

dfs-ts(v,R) {

visited[v] <- yes

for each x adjacent to v do

if (visited[x] ==no) then

dfs-ts(x,R);

add v at the front of the linked list R

}

}