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

그래프 순회는 그래프의 모든 정점을 방문하는 방법임

순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음.

먼저 깊이 우선 탐색에 대해 알아보자

unexplored vertex는 방문하지않은 정점이고 visted vertex는 한번 지나온 정점임

A -> B -> C로  순서일 때,  C -> A가 연결되있음. 하지만 A는 이미 지나온 정점임.

C -> A Edge를 back edge로 표기함 이제 C는 D로 가거나 E로 갈 수 있음.

파이썬으로 구현해보면

def DFS(g, u, discovered):
 
    for e in g.incident_edges(u):
        v = e.opposite(u)
        if v not in discovered: 
            discovered[v] = e
            DFS(g, v, discovered)
 
def DFS_complete(g):
 
    forest = {}
    for u in g.vertices():
        if u not in forest:
            forest[u] = None
            DFS(g, u, forest)
    return forest

g = graph

forest = 이미 지나온 정점 , 딕셔너리로 생성

1단계 모든 정점에 대해서 루프를 돔

2단계 정점이 forest에 없다면 u 에 대한 forest를 초기화 해줌

3단계 DFS()를 호출해서 u의 인접한 모든 edge에 대해서 확인을 함

4단계 v는 인접한 정점임  v를 방문하지 않았으면 forest(discovered)에 e를 추가함 

이과정을 계속 반복하면 모든 정점을 방문함.