[알고리즘] BFS (Breath First Search)

너비 우선 탐색 BFS
(Breath First Search)

: 탐색 노드로부터 제일 가까운 노드부터 탐색하는 알고리즘이다. 또한, 가까운 노드부터 우선 순위를 가져야 하기 때문에, 후입 선출 방식인 Queue를 사용하여 구현 할 수 있다.

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내고, 인접 노드들 중 방문 하지 않는 노드들을 모두 큐에 삽입하고 방문 처리한다.
3. 2번 과정을 반복한다.
   
   

사용하는 경우

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우 모든 친구 관계를 다 살펴봐야 할지도 모르지만, 너비 우선 탐색의 경우 Ash와 가까운 관계부터 탐색

코드

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

장점

• 모든 경로를 탐색 할 때 최단 경로를 보장한다.
• 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.
  
  

단점

• 노드 수가 많을수록 탐색 가지가 급격히 증가함에 따라 보다 많은 메모리를 필요로 한다.
• 많은 노드를 저장하기 때문에 DFS보다 큰 공간 복잡도를 가진다.