BFS ( 너비 우선 탐색 )

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

너비 우선 탐색( BFS : Bredth-First Search )

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 깊게( Deep ) 탐색하기 전에 넓게( Wide ) 탐색하는 것이다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택

BFS의 장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
• 단순 검색 속도가 깊이 우선 탐색( DFS )보다 빠르다.
• 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
• 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

BFS의 단점

• 재귀호출을 사용하는 DFS와는 달리 큐에 다음 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
• 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

BFS 구현

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

print(bfs(graph, 'A'))

~~>
['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

start_node A가 처음에 bfs함수에 들어가게 되고 need_visit에 append 된다.
node에는 A가 들어가게 되고, 처음 visited에는 A가 없으므로 need_visit에 graph['A']의 값이 extend 된다. (-> ['B', 'C'])

이 과정을 계속 반복하게 된다.

시간 복잡도

• 노드의 수 : V
• 간선의 수 : E

인접 리스트로 표현된 그래프 ( 위의 같은 경우 )

• $O(V + E)$

인접 행렬로 표현된 그래프

• $O(V^2)$