DFS (깊이 우선 탐색)

DFS는 Depth-First Search의 약자며 깊이를 우선적으로 탐색하는 알고리즘이다. DFS는 Stack 자료구조 혹은 Recursive function, 재귀함수를 이용한다. 위의 그림과 같이 0으로 시작하여 연결된 제일 작은 노드인 1 그리고 1과 연결된 3, 4를 탐색하며 작은 값 방향으로 탐색한다. 이와 같이 마지막 노드 즉 제일 깊은 노드까지 탐색한다 하여 깊이 우선 탐색이라 한다.

Python 예제

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


graph = [
	[], 
        [2, 3, 8], 
        [1, 7], 
        [1, 4, 5], 
        [3, 5], 
        [3, 4], 
        [7], 
        [2, 6, 8], 
        [1, 7]
 ]

visited = [False] * 9

dfs(graph, 1, visited)

위의 graph는 2차원 리스트로 각 노드가 연결된 정보를 표시한다. 여기서 주로 1번째 노드로 시작하기에 0번째 노드는 비워두었다. 그리고 1로 시작하여 작은 값순으로 1과 연결된 노드는 2, 3, 8이고 2와 연결된 노드는 1, 7이다.