[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal) 그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 v ohaengsa.tistory.com 방향그래프는 기존의 그래프와 달리 정점과 간선 사이에 방향성을 추가한 그래프임 1단계. 임의의 점을 선택함 예제에서는 A를 선택했다고 가정함 2단계 A는 C, D, B로 갈 수 있음. B, D, E 순서로 방문하였다고 가정함 3단계. E는 A를 제외하고 갈 수 있는 곳이 없음. 하지만 A는 이미 방문함. E -> A를 Backedge(노란색)으로 표시함 4단계. 뒤로 돌아가서 B..

그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 visted vertex는 한번 지나온 정점임 A -> B -> C로 순서일 때, C -> A가 연결되있음. 하지만 A는 이미 지나온 정점임. C -> A Edge를 back edge로 표기함 이제 C는 D로 가거나 E로 갈 수 있음. 파이썬으로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def DFS(g, u, discovered): for e in g.incident_edges(u): v = e.opposite(u) if v not in discovered: dis..