DFS - 깊이우선탐색

DFS는 깊이 우선 탐색으로 최대한 깊숙히 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

아래의 Graph를 통해 DFS에 대해 알아보자.

Graph

Graph

Code로 보는 Graph

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

DFS 탐색하기

DFS 탐색 순서

간단한 DFS 알고리즘

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

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


graph = [
    [],  # root_node
    [2, 3, 8], # 1의 Links
    [1, 7],    # 2의 Links
    [1, 4, 5], # 3의 Links
    [3, 5],    # 4의 Links
    [3, 4],    # 5의 Links
    [7],       # 6의 Links
    [2, 6, 8], # 7의 Links
    [1, 7]     # 8의 Links
]

visited = [False] * len(graph)

dfs(graph, 1, visited) # result : 1 2 7 6 8 3 4 5 

탐색 과정

1.  1이 시작노드 - 1의 Link중 가장 작은 값부터 탐색, 시작노드를 방문함으로 표시 visited[1] = True

    [2, 3, 8] -> 가장 작은 값인 2를 방문했다는 표시를 함 visited[2] = True

    visited => [False, True, False, False, False, False, False, False, False]

    visited => [False, True, True, False, False, False, False, False, False]

 

2.  2를 이어 더 깊게 내려가기 위해 2의 링크 노드 탐색

    [1, 7] -> 1은 방문한 노드이기 때문에 넘어감

    [1, 7] -> 연결되있고 방문하지 않으면서 가장작은 값 7노드를 방문함 visited[7] = True

    visited => [False, True, True, False, False, False, False, True, False]

 

3.  7를 이어 더 깊게 내려가기 위해 7의 링크 노드 탐색

    [2, 6, 8] -> 2는 방문한 노드이기 때문에 넘어감

    [2, 6, 8] -> 연결되있고 방문하지 않으면서 가장작은 값 6노드를 방문함 visited[6] = True

    visited => [False, True, True, False, False, False, True, True, False]

 

4.  6을 이어 더 깊게 내려 가려 했으나 방문하지 않은 노드가 없기 때문에 위로 올라감

    [7] -> 7은 방문한 노드이고 더 탐색한 노드가 없기에 위로 올라감

    

5.  7를 이어 더 깊게 내려가기 위해 7의 링크 노드 탐색

    [2, 6, 8] -> 2와 6은 방문한 노드이기 때문에 넘어감

    [2, 6, 8] -> 연결되있고 방문하지 않으면서 가장작은 값 8노드를 방문함 visited[8] = True

    visited => [False, True, True, False, False, False, True, True, True]

 

6.  8을 이어 더 깊게 내려 가려 했으나 방문하지 않은 노드가 없기 때문에 위로 올라감

    [1, 7] -> 1과 7은 방문한 노드이고 더 탐색한 노드가 없기에 위로 올라감

    8 -> 7 -> 2 -> 1 까지 모두 방문한 노드이기에 start node인 1까지 올라감

    

7.  1의 연결 노드중 방문하지 않은 다른노드를 탐색함

    [2, 3, 8] -> 2와 8은 방문한 노드이기 때문에 넘어감

    [2, 3, 8] -> 연결되있고 방문하지 않으면서 가장작은 값 3노드를 방문함 visited[3] = True

    visited => [False, True, True, True, False, False, True, True, True]

 

8. 3를 이어 더 깊게 내려가기 위해 3의 링크 노드 탐색

    [1, 4, 5] -> 1은 방문한 노드이기 때문에 넘어감

    [1, 4, 5] -> 연결되있고 방문하지 않으면서 가장작은 값 4노드를 방문함 visited[4] = True

    visited => [False, True, True, True, True, False, True, True, True]

 

9. 4를 이어 더 깊게 내려가기 위해 4의 링크 노드 탐색

    [3, 5] -> 3은 방문한 노드이기 때문에 넘어감

    [3, 5] -> 연결되있고 방문하지 않으면서 가장작은 값 5노드를 방문함 visited[5] = True

    visited => [False, True, True, True, True, True, True, True, True]

 

10. 모든 노드를 탐색 했으므로 DFS 탐색 종료.

     - 재귀문을 타고 다시 시작노드까지 올라간 뒤 종료.