12-04 위상 정렬(Topological Sort)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

 

1.위상정렬(Topological Sort)

 1)정의

 -그래프에서 위상이란 정점과 정점의 관계 속에서 가지는 위치를 뜻한다.

 -간선은 정점과 정점 사이의 관계를 나타내고 정점의 입장에서 간선은

 들어가는 간선인 진입간선(Incoming Edge), 나오는 간선인 진출간선(Outgoing Edge)으로 나눌 수 있다.

 -간선을 통해 정점들 간의 누가 진출(앞)/진입(뒤)하는 관계에서 정점들 간의 위치를 나타낸다. 

 -위상 정렬은 간선들의 진출/진입의 방향이 한 방향이 되도록 정렬하는 알고리즘을 말한다.

2)과정

 

3)깊이 우선 탐색을 이용한 위상 정렬

4)우선 깊이 탐색 코드