BFS를 이용하여 DAG그래프 인지 판별

정의

  DAG : ( Directed Acyclic Graph) 비순환 그래프 구조 (Ex : Tree)

  BFS : ( Breadh-First Search) 넓이 우선 탐색 (비순환 그래프에서 Level를 찾을때 주로 사용)

  Indegree : 부모 노드로 부터 들어오는 간선 개수

 

Algorithm

1. 각 노드의 indegree를 구한다.
2. indegree가 0 인 노드를 queue에 push한다
   1. 해당 노드는 root노드가 된다
3. BFS로 각 노드를 순회 하면서 방문되 노드의 indegree를 차감 시키고, indegree가 0일때 queue에 push후 카운트를 증가 시킨다.
4. 노드의 순회가 끝난후 카운트의 수가 노드의 수와 같으면 DAG그래 프다