[TIL] 105. BFS/DFS

키워드

• 그래프 탐색
• BFS(Breadth First Search; 너비 우선 탐색)
• DFS(Depth First Search; 깊이 우선 탐색)
• 스택, 큐, 재귀 활용

그래프 순회

• 순회 : 모든 노드를 방문하면서 탐색하는 알고리즘
• 그래프 탐색 알고리즘으로는 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)이 있다.

[알고리즘 : 탐색] BFS(너비 우선 탐색)

• 현재 노드에 연결된 가까운 노드들부터 탐색
• 자료구조 중 큐(queue)를 통해 구현
• 장점 : 너비를 우선으로 탐색하기 때문에 최단 경로를 찾기에 유리하다.
• 단점 : 재귀로도 구현 가능한 DFS와 달리 큐를 이용해 탐색할 노드들을 저장하기 때문에 메모리를 많이 차지한다.

큐를 이용한 BFS 구현

## 그래프(bfs_graph)가 따로 주어져야함

def bfs_queue(start_node, bfs_graph):
    bfs_list = [start_node]
    que = [start_node]

    while que:
        node = que.pop(0)
        for i in bfs_graph[node]:
            if i not in bfs_list:
                bfs_list.append(i)
                que.append(i)
    return bfs_list

[알고리즘 : 탐색] DFS(깊이 우선 탐색)

• 현재 노드에서 갈 수 있는 점들까지 깊게 들어가면서 탐색
• 자료구조 중 스택(stack)을 통해 구현 또는 재귀함수를 이용하여 구현
• 장점 : BFS에 비해 메모리(저장공간)의 필요성이 적다. 찾아야하는 노드가 깊은 단계에 있을수록 유리하다.
• 단점 : 찾은 답이 최단 경로라는 보장이 없다.

스택을 이용한 DFS 구현

## 그래프(dfs_graph)가 따로 주어져야함

def dfs_stack(start_node):
    dfs_list = []
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in dfs_list:
            dfs_list.append(node)
            stack.extend(dfs_graph[node])
    return dfs_list

 

재귀를 이용한 DFS 구현

## 그래프(dfs_graph)가 따로 주어져야함

def dfs_recur(node, dfs_list=[]):
    dfs_list.append(node) 

    for i in dfs_graph[node]: 
        if i not in dfs_list:
            dfs_recur(i)
    return dfs_list