[Python] DFS & BFS - DFS와 BFS를 쓰는 상황

자바로 dfs와 bfs를 공부한적이있는데, 파이썬으로 다시 해보면서 개념정리와, 어떤 상황에서 유리한지 정리해보고자 한다,

 

DFS & BFS

---

DFS란

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]

• dfs는 그래프의 노드를 갈 수 있는 데 까지 끝까지 방문하는 것이다.
• 노드를 순서대로 목적지에 도달할 때 까지 방문하면서, 각 노드에서 또 방문할 수 있는 위치를 저장해 둔다.
• 노드가 끝까지 갔다가 다시 한칸 뒤로 돌아와, 갈 수 있는 방향을 탐색한다.
• 따라서 재귀적이고 / 스택을 이용할 수 있다.
• Depth First Search

 

BFS란

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]

• bfs는  노드에서 인접한 노드를 먼저 방문한다.
• 한 노드에서 갈수있는 모든 경우의 수를 저장한 후, 순서대로 방문한다.
• 이를 반복하기 위해서 큐를 사용한다.
• 큐에 방문할 위치를 저장함으로써 순서대로 방문이 가능하다.
• Breadth First Search

탐색 노드의 경우의 수

 

 

1. DFS 구현 - Python

dfs 그래프

[재귀를 이용]

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 i in adjacent_graph[cur_node] :
        if i not in visited_array:
            dfs_recursion(adjacent_graph,i,visited_array)


    return


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

 

[스택 이용]

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

 

 

2. BFS 구현 - Python

 

[재귀를 이용]

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


def bfs_queue(adj_graph, start_node):
    queue=[start_node]
    visited =[]

    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)
    # 구현해보세요!
    return visited



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