개발자 블로그

DFS & BFS 본문

CS/자료구조

DFS & BFS

hayongwoon 2022. 7. 14. 13:40

DFS

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 = [] # 방문한 걸 저장하기 위한 배열

1. 우선 탐색 시작 노드를 1로 잡겠습니다!

2. 현재 방문한 노드인 1을 visited 에 추가합니다. # visited -> [1]

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [2, 5, 9] 입니다. 2 에 방문합니다.

4. 현재 방문한 노드인 2을 visited 에 추가합니다. # visited -> [1, 2]

5. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들은 [3] 입니다. 3에 방문합니다.

6. 현재 방문한 노드인 3을 visited 에 추가합니다. # visited -> [1, 2, 3]

7. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들은 [4] 입니다. 4에 방문합니다.

8. 현재 방문한 노드인 4을 visited 에 추가합니다. # visited -> [1, 2, 3, 4]

9. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없습니다. 7로 돌아갑니다.

7. 인접한 노드들인 [2, 4] 에서 방문하지 않은 것들이 없습니다. 5로 돌아갑니다.

5. 인접한 노드들인 [1, 3] 에서 방문하지 않은 것들이 없습니다. 3로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [5, 9] 입니다. 5에 방문합니다.

10. 현재 방문한 노드인 5를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5]

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들은 [6, 8] 입니다. 6에 방문합니다.

12. 현재 방문한 노드인 6를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6]

13. 인접한 노드들인 [5, 7] 에서 방문하지 않은 것들은 [7] 입니다. 7에 방문합니다.

14. 현재 방문한 노드인 7를 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7]

15. 인접한 노드들인 [6] 에서 방문하지 않은 것들이 없습니다. 11로 돌아갑니다.

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들은 [8] 입니다. 8에 방문합니다.

16. 현재 방문한 노드인 8을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8]

17. 인접한 노드들인 [5] 에서 방문하지 않은 것들이 없습니다. 11로 돌아갑니다.

11. 인접한 노드들인 [1, 6, 8] 에서 방문하지 않은 것들이 없습니다. 3으로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [9] 입니다. 9에 방문합니다.

18. 현재 방문한 노드인 9을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

19. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들은 [10] 입니다. 10에 방문합니다.

20. 현재 방문한 노드인 10을 visited 에 추가합니다.  # visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

21. 인접한 노드들인 [9] 에서 방문하지 않은 것들이 없습니다. 19로 돌아갑니다.

19. 인접한 노드들인 [1, 10] 에서 방문하지 않은 것들이 없습니다. 3로 돌아갑니다.

3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들이 없습니다. 1로 돌아갑니다.

1. 끝났습니다.


자... 어마어마한 내용들이 있었는데요!
이 코드를 보면 어떤 순서대로 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 adjacent_node in adjacent_graph[cur_node]:
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)

    return visited

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

*탈출 조건이 없어도 그래프의 노드가 유한하기에 돌아볼 노드가 없다면 종료가 된다. 하지만, 노드가 너무나 많다면 이도 리컬젼 에러가 발생할 수 있다.  이럴 때에는 스택 자료구조를 활용해서 dfs를 구현해볼 수 있다.

 

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]
}
visited = [] # 방문한 걸 저장하기 위한 배열
queue = [1] # 시작 노드인 1을 넣어둔다.

1. 현재 큐에서 가장 처음에 넣은 1을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1]

2. 인접한 노드들인 [2, 3, 4] 에서 방문하지 않은 것들인 [2, 3, 4]를 queue 에 추가합니다. 
# queue -> [2, 3, 4] visited -> [1]

3. 현재 큐에서 가장 처음에 넣은 2을 빼서, visited 에 추가합니다. 
# queue -> [3, 4] visited -> [1, 2]

4. 인접한 노드들인 [1, 5] 에서 방문하지 않은 것들인 [5]를 queue 에 추가합니다. 
# queue -> [3, 4, 5] visited -> [1, 2]

5. 현재 큐에서 가장 처음에 넣은 3을 빼서, visited 에 추가합니다. 
# queue -> [4, 5] visited -> [1, 2, 3]

6. 인접한 노드들인 [1, 6, 7] 에서 방문하지 않은 것들인 [6, 7]를 queue 에 추가합니다. 
# queue -> [4, 5, 6, 7] visited -> [1, 2, 3]

7. 현재 큐에서 가장 처음에 넣은 4을 빼서, visited 에 추가합니다. 
# queue -> [5, 6, 7] visited -> [1, 2, 3, 4]

8. 인접한 노드들인 [1, 8] 에서 방문하지 않은 것들인 [8]를 queue 에 추가합니다. 
# queue -> [5, 6, 7, 8] visited -> [1, 2, 3, 4]

9. 현재 큐에서 가장 처음에 넣은 5을 빼서, visited 에 추가합니다. 
# queue -> [6, 7, 8] visited -> [1, 2, 3, 4, 5]

10. 인접한 노드들인 [2, 9] 에서 방문하지 않은 것들인 [9]를 queue 에 추가합니다. 
# queue -> [6, 7, 8, 9] visited -> [1, 2, 3, 4, 5]

11. 현재 큐에서 가장 처음에 넣은 6을 빼서, visited 에 추가합니다. 
# queue -> [7, 8, 9] visited -> [1, 2, 3, 4, 5, 6]

12. 인접한 노드들인 [3, 10] 에서 방문하지 않은 것들인 [10]를 queue 에 추가합니다. 
# queue -> [7, 8, 9, 10] visited -> [1, 2, 3, 4, 5, 6]

13. 현재 큐에서 가장 처음에 넣은 7을 빼서, visited 에 추가합니다. 
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

14. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

15. 현재 큐에서 가장 처음에 넣은 8을 빼서, visited 에 추가합니다. 
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

16. 인접한 노드들인 [4] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

17. 현재 큐에서 가장 처음에 넣은 9을 빼서, visited 에 추가합니다. 
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

18. 인접한 노드들인 [5] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

19. 현재 큐에서 가장 처음에 넣은 10을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

20. 인접한 노드들인 [6] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

21. 현재 큐에서 꺼낼 것이 없습니다. BFS 가 끝났습니다.


자... 어마어마한 내용들이 있었는데요!
이 코드를 보면 어떤 순서대로 BFS 가 이루어지는 지 조금은 이해가 가실 것 같습니다.
모든 순서를 외우실 필요는 없습니다 다만! 탐색의 순서와 느낌에 대해 이해가셨으면 좋겠습니다.
from collections import deque

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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):
    visited = []
    q = deque()
    q.append(start_node)

    while q:
        current_node = q.popleft()
        visited.append(current_node)
        for adj_node in adj_graph[current_node]:
            if adj_node not in visited:
                q.append(adj_node)

    return visited


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

'CS > 자료구조' 카테고리의 다른 글

컴퓨터에서 0.1은 왜 0.1이 아닐까  (0) 2022.08.16
해쉬 테이블  (0) 2022.07.06
Array and LinkedList  (0) 2022.07.05
'CS/자료구조' Related Articles more