[BFS] 알고리즘 - 너비 우선 탐색 (BFS, Breadth First Search)

너비 우선 탐색 (BFS, Breadth First Search)

한 노드에서 시작한 후 시작 노드의 인접한 노드부터 탐색하는 방법이다.

가까운 노드부터 탐색하는 알고리즘 이다.

시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 있는 노드는 마지막에 방문하는 방식이다.

넓게 탐색하는 방식이다.

 

일반적으로 선입선출 방식인 큐 자료구조를 활용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색이 이루어진다.

 

특징 

• 여러 갈래중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우에는 DFS는 무한루프에 빠져 종료되지 못하지만, BFS는 동시에 탐색이 진행되기때문에 탐색이 완료될 수 있다.
• 모든길을 한번씩 탐색하기 때문에 시작점에서 끝점까지의 최단경로를 알아낼 수 있다.
• 일반적인 경우 수행 시간이 DFS보다 좋은 편이다.

 

사용 용도

• 두 노드 사이의 최단경로를 구할 때
• 두 노드 사이의 임의의 경로를 찾을 때

 

구현 방법 

• 선입 선출로 탐색한다. 
• 일반 적으로 큐를 사용해서 구현한다.

 

기본적인 탐색 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

 

시간 복잡도 (N : 정점의 수 , E : 간선의 수)

• 인접리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

 

장점 : 출발노드에서 목표노드까지 최단거리를 보장한다.
단점 : 경로가 매우 길 경우 탐색가지의 급격한 증가에 따라 많은 공간을 필요로한다.
          해가 존재하지 않는 유한그래프의 경우에 모든 그래프를 탐색 후 실패로 종료된다.
          무한 그래프의 경우에는 결코 해를 찾지 못하고 끝내지도 못한다.

 

 

구현 방법

from collections import deque

def BFS(graph, root):
	visited = []
    q = deque([root])
    
    while q:
    	n = q.popleft()
        for node in graph[n]:
        	if node not in visited:
            	   visited.append(node)
                   q.append(node)

 

 

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

---

BFS 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스