DFS 구현하기

DFS

DFS는 깊이우선탐색이라고도 하며, 인접한 노드를 끝까지 모두 탐색한 후 방문하지 않은 노드가 없다면 다시 돌아가서 탐색하는 과정을 반복하여, 모든 노드가 방문하는 방법이다.

 

1. 재귀함수로 구현하기

시작 노드를 입력 받아 방문한 노드에 넣고, 인접한 노드가 방문하지 않은 노드라면, 함수를 재귀적으로 다시 호출한다.

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []


def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjecent_node in adjacent_graph:
        if adjecent_node not in visited_array:
            dfs_recursion(adjacent_graph,adjecent_node,visited_array)
    return


dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

-> 코드가 간단하지만, 깊이가 무한정 깊다면 에러가 발생할 수 있다.

 

2. 스택으로 구현하기

먼저 스택에 시작하는 노드를 넣은 후, 이를 스택에서 뺸 후 방문한 노드에 넣는다.

그 후 인접한 노드 중 방문하지 않은 노드를 스택에 추가하고, 이 과정을 스택이 빌 때 까지 반복한다. 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!