탐색 알고리즘 BFS (2021/02/21)

BFS는 너비 우선 탐색을 뜻한다.

 

DFS가 깊이 우선 탐색을 했던것과 다르게 BFS는 가까운 노드부터 탐색한다.

 

다르게 말해, 시작 노드로부터 거리가 같은 노드들이 한번에 탐색된다.

 

또, DFS는 스택과 재귀함수를 이용했지만 BFS에서는 큐를 이용한다.

 

 

동작 순서는

 

탐색 시작 노드를 큐에 삽입하고 방문처리를 한다. 그리고 큐에서 노드를 꺼내고 방문하지 않은 인접 노드를 모두 큐에 삽입한다. 이를 반복한다.

 

예제를 풀어보면

 

graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

 

그래프 입력이 들어올 때

 

from collections import deque

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

 

bfs 함수부터 살펴보면 탐색 시작 노드를 큐에 넣고 이 노드를 방문처리한다. 그리고 큐가 빌 때까지 while문을 반복한다. 큐에서 노드를 꺼내고 이를 출력한다. 그리고 그래프의 입력 값에서 방문하지 않은 노드를 큐에 넣는다. 그리고 방문처리한다. 이를 while문으로 반복한다.

 

이 결과로 

 

1 2 3 8 7 4 5 6 

 

가 출력된다.

 

 

DFS가 스택과 재귀함수를 이용한 것과 다르게 BFS는 큐를 이용하므로 deque을 import해주어야 한다.