[알고리즘] DFS 와 BFS 깊이 우선 탐색, 너비 우선 탐색

DFS/ BFS

자료의 검색, 트리나 그래프를 탐색하는 방법

한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 올라와서 다음을 탐색하여 검색하는 것.

 

 

DFS (깊이 우선 탐색)

노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다

끝까지 방문하면 다시 돌아와서 다시 끝까지 방문한다.

이렇게 그래프가 있을 때 깊이 우선은 숫자 순서대로 탐색한다

1 2 3 4 까지 갔다가 다시 1로 올라와서 5 6 7 을 방문하고 다시 5로 올라와서 8을 방문하고

다시 1로 올라와서 9 10을 방문한다.

 

재귀함수로 이를 표현한다

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 = []
 
 
# 1.시작노드(루트 노드) 인 1부터 탐색합니다
# 2. 현재 방문한 노드를 visited_array에 추가합니다
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문합니다.
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph:
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)
    return
 
 
dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

그런데 재귀함수로 하면 무한정 깊어지는 노드가 있는 경우 에러가 생길 수도 있다.

 

스택을 이용하면 재귀없이 구현할 수 있다.

1. 루트 노드를 스택에 넣는다.

2. 현재 스택의 노드를 빼서 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 누드를 스택에 추가한다.

4. 2부터 반복한다.

5. 스택이 비면 탐색을 종료한다.

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}
 
# 1. 시작 노드를 스택에 넣는다
# 2. 현재 스택의 노드를 빼서 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가한다.
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] 이 출력되어야 합니다!

1. 시작 노드인 1을 스택에 넣는다.

2. 현재 스택에서 가장 마지막 원소를 빼서 visited에 추가한다.

3. 인접한 노드 2 5 9 에서 방문하지 않은 2 5 9를 스택에 추가한다.

4. 현재 스택의 가장 마지막 원소인 9를 visited에 추가한다.

5. 9의 인접 노드인 1 10 중에서 방문하지 않은 10을 스택에 추가한다.

6. 현재 스택에서 가장 마지막 원소인 10을 빼서 visited에 추가한다.

7. 10의 인접 노드인 9 중에서 방문하지 않은 원소가 없으니 추가하지 않는다.

8. 현재 스택에 2 5 중에서 마지막 5를 빼서 visited에 추가한다.

.... 반복

스택에 꺼낼 것이 없을 때까지 반복

 

 

---

BFS(너비 우선 탐색)

BFS는 현재 가장 인접한 노드 먼저 방문해야한다.

인접한 노드 중 방문하지 않은 모든 노드를 저장해두고

가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

큐를 사용하여 구현한다.

아까와 달리 이 순서대로 탐색을 한다.

 

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}
 
# 1. 시작 노드를 큐에 넣는다.
# 2. 현재 큐의 노드를 빼서 visited에 추가합니다.
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
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] 이 출력되어야 합니다!

 

1. 시작 노드인 1을 큐에 넣는다.

2. 현재 큐에서 가장 처음에 넣은 1을 빼서 visited에 추가한다.

3. 1의 인접 노드인 2 3 4 에서 방문하지 않은 2 3 4 를 큐에 추가한다.

4. 현재 큐에서 가장 처음 넣은 2를 빼서 visited에 추가한다.

5. 2의 인접한 노드인 1 5 중에서 방문하지 않은 5를 큐에 추가한다.

6. 현재 큐에서 가장 처음 원소인 3을 빼서 visited에 추가한다....

큐에서 꺼낼 것이 없을 때까지 반복