[파이썬 자료구조] 방향그래프 (Directed Graph)

 

[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal)

---

방향그래프는 기존의 그래프와 달리 정점과 간선 사이에 방향성을 추가한 그래프임

1단계. 임의의 점을 선택함 예제에서는 A를 선택했다고 가정함

2단계 A는 C, D, B로 갈 수 있음. B, D, E 순서로 방문하였다고 가정함

3단계. E는 A를 제외하고 갈 수 있는 곳이 없음. 하지만 A는 이미 방문함. E -> A를 Backedge(노란색)으로 표시함

4단계. 뒤로 돌아가서 B로 감. B->E의 길이 존재하지만 E는 이미 방문함. Forward edge(보라색)으로 표시함.

Backedge와 Forward edge의 차이점은 E->A는  위로 올라가는 순서이고 B->E는 아래로 내려가는 순서임

5단계. B에서 더이상 갈때가 없으니까 A로 돌아감 A는 이제 C나 D로 갈 수 있음

6단계. C를 먼저 방문한다고 가정하면 C는 E와 D로 갈 수 있지만 이미 방문한 것들임. Cross edge(초록색)으로 표시함

이것은 하나의 트리로 표현될 수있는데 E,D는 이미 B의 자식들이기 때문에 C는 E와 D를 가질 수 없기 때문임

7단계. 마지막 남은 D로 향하지만 이미 방문한 정점이고 A보다 순서가 아래이기 때문에 Forward edge로 표시함.

Reachability: 한 정점에서 도달할 수 있는 모든 정점들

Strong connectivity: 한 정점에서 모든 정점에 도달할 수 있는 경우