위상 정렬 개념 C

사전 지식

DAG이란?

방향 비싸이클 그래프(Directed Acyclic Graph)

방향 사이클이 존재하지 않는 방향 그래프를 말한다. 다시 제자리로 돌아올 수 있는 경로가 없는 그래프.

위상정렬이란?

DAG로부터 위상 순서를 얻는 절차이다.

 

 

자기한테 오는 간선이 없는 정점들이 맨 앞에 온다.

여기서는 A와 D가 맨 앞에 올 수 있다.

1번과 2번으로부터 들어오는 간선을 제외한 나머지 간선들을 생각해서 제일 앞에 올 수 있는 정점을 구한다.

 

번호를 다 매기지 않았는데 만약 진입간선이 있는 정점들밖에 남지 않았다면 이는 무엇을 의미하는가?

⇒ 싸이클이 있다는 것을 의미한다.(DAG이 아니다!)