BFS(너비 우선 탐색)

지난 번에는 그래프 탐색 알고리즘 중, DFS에서 알아보았다. 오늘은 너비 우선 탐색인 BFS에 대해 알아보자.
BFS는 루트 노드나 임의의 노드에서 시작하여 인접한 노드(바로 옆 이웃)를 먼저 모두 확인한 뒤 다음 Depth를 탐색한다. BFS는 큐(queue)를 사용하여 구현할 수 있다. 또한 DFS와는 다르게 재귀적으로 작동하지 않고, FIFO 원리로 탐색을 진행한다.

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

아래 사진을 참고하여 이해를 도울 수 있다.

출처: 이지섭

BFS는 두 노드 사이의 최단경로를 탐색할 경우에 활용하기 좋은 방식이다. 멀리 떨어진 노드는 나중에 탐색하는 원리를 가지고 있기 때문이다 . 또한 단순 검색 속도가 DFS보다 빠르다.

하지만 BFS는 정점들을 큐에 저장해야 하므로 저장공간이 많이 필요하다는 단점이 존재한다.

파이썬을 사용한 BFS의 코드 구현은 다음과 같다.

from collections import deque
def bfs(graph,start,visted):
	queue=deque([start])
    visted=[start]=True
    while queue:
    v= queue.popleft()
    print(v,end=' ')
    for i in graph[v]:
    	if not visted[i]:
        	queue.append(i)
            visted[i]=True
graph = [
    [],
    [2,3,4],
    [1,5],
    [1,6],
    [1,7],
    [2,8],
    [3,9],
    [4,10],
    [5],
    [6],
    [7]
]

visted = [False]*(10+1)
dfs(graph,1,visted)

실행결과 
> 1 2 3 4 5 6 7 8 9