BFS (너비 우선 탐색)

BFS

많은 양의 데이터 중에서 원하는 데이터를 찾는 탐색의 기법 중 하나로

Breadth First Search 말 그대로 너비 우선 탐색입니다.

 

BFS 이해 1

 

그림과 같이 한 경로에서 루트 노드에서 가까운 순서대로 서서히

다음의 탐색을 진행하는 탐색법이라고 보시면 되겠습니다.

 

BFS 이해 2

 

 

노드 간의 Level을 나누어, 가까운 곳부터 탐색한 뒤, +1을 해주면서 Level을 나누어 탐색하는 것으로 이해하시면 되겠습니다.

 

보통 DFS와 주로 비교하는데 각각의 장단점이 존재한다고 보시면 되겠습니다.

 

DFS와 BFS 비교

 

 

장점

• 목표 노드가 가까울수록 빠르게 도달할 수 있습니다.
• 목표 노드를 찾는다면 이것이 최단 경로라고 확신할 수 있습니다.

 

단점

• 저장공간이 DFS에 비해 더 크게 요구됩니다. (다음에 탐색할 노드들을 저장하기 때문에)
• 노드의 수 전체가 늘어날 수록 비효율적일 수 있습니다.

 

특징

• 시간 복잡도는 V * O(V) = O (V^2) 입니다.

 

구현 코드 ( Python )

def bfs(graph, start_node):
    visit = list()
    queue = list()

    queue.append(start_node)

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

    return visit