[자료구조] 깊이 우선 탐색(dfs) 원리 및 방법, 알고리즘

그래프의 순회나 탐색은 하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산이다. 그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있다.

 

깊이 우선 탐색의 경우, 먼저 하나의 정점을 방문한다. 그리고 이웃한 정점으로 갈 수 있으면 무조건 이웃 중 하나로 방문하고(단, 과거에 방문하지 않은 정점이어야한다.) 이를 계속 반복하여 시작점에서 점점 깊이가 깊어지는 노드로 전진시킨다.

만약 방문 가능한 이웃 정점이 없다면 왔떤 경로 상의 가장 최근에 방문했던 정점으로 돌아가서 그 정점의 이웃 노드 방문을 시도한다. 이 때 스택을 이용한다.

 

알고리즘은 다음과 같은 절차로 구성된다.

 

1) 먼저 시작 정점 v를 결정하고, 방문한다.

2) 정점 v에 인접하고 아직 방문하지 않은 한 정점 w를 선택한다. 방문하지 않은 정점이 없다면 스택에서 pop을 하고, 만약 방문하지 않은 정점이 있다면 정점 v를 스택에 push하고 pred(w)를 v라고 셋팅한다. 그리고 w를 v로 하여 다시 시작정점을 방문한다.

방문하지 않은 정점이 있는 경우 스택에서 pop을 한다고 했는데, 이는 다시 두 가지 케이스로 나뉜다. 공백일 경우 알고리즘이 종료되지만, 공백이 아니라면 꺼낸 정점을 v로 하여 아직 방문하지 않은 정점 w를 재선택한다. 이를 계속 반복한다.

 

 

[파이썬으로 구현한 dfs 코드] 

 

def dfs(graph, start):
    stack = [start]
    visited = set()
    pred = {}

    while stack:
        v = stack.pop()

        if v not in visited:
            visited.add(v)
            print("Visit:", v)

            # 인접한 정점 중 아직 방문하지 않은 정점을 스택에 추가
            for w in graph[v]:
                if w not in visited:
                    stack.append(w)
                    pred[w] = v

    return pred

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

start_vertex = 'A'
predecessors = dfs(graph, start_vertex)

# 결과 출력
print("Predecessors:", predecessors)