그래프 - Graph(3. DFS in directed graphs)

3. DFS in directed graphs

DFS 방향 그래프 / DFS spanning tree

1. DFS tree 엣지의 종류 

DFS tree edges type

• Tree edge: DFS에 포함되는 엣지
• Forward edge: 후손이 아닌 관계로 가는 엣지 
• Backward edge: 조상으로 가는 엣지
• Cross edge: 아무 관계도 아닌 vertex(노드)를 연결하는 관계 

 

2. DAG (Directed Acyclic Graph)

DAG는 비순환그래프로 사이클이 존재하지 않고 일방향성만 갖는 것을 의미한다.

DAG

• source: 나가는 엣지만 있는 정점
• sink: 들어오는 엣지만 있는 정점

 

3. DAG 성질

• 어떤 그래프에 사이클이 있다면 Back edge가 있다.
• dag의 모든 edge는 더 낮은 post number로 간다.
• 어떤 DAG는 적어도 하나의 source와 sink를 가진다. 

 

 

4. DFS 정리

종류	목적	작업	시간복잡도
DFS	모든 정점 순회	모든 정점과 모든 간선(edge) 방문	O(n) + O(M)