위상정렬

순서가 있는 작업을 차례로 수행하기 위해 결정짓는 알고리즘

 

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는것

 

- DFS 위상정렬

1. dfs

2. 정점을 역순으로 스택에 쌓고

3. 스택을 쌓은것을 꺼내면서 출력한다.

-

 

-BFS 위상정렬

- 진입 차수

: 특정노드로 들어오는 간선의 개수

진출 차수

: 특정노드에서 나가는 간선의 개수

 

1. 각노드들의 진입차수계산

2. 진입차수가 0인 정점 모두 큐에 삽입

3. 큐에서 노드간에 연결된간선제거

4. 제거로 인해 진입 차수가 0이된 노드 큐에 삽입

5. 큐가 비면 종료