BFS(Breadth-First search)
탐색 알고리즘의 일종이다. 그래프로 데이터가 주어졌을 때, 시작 노드부터 거리가 같은 노드부터 순차적으로 탐색하는 알고리즘, 즉 너비를 우선적으로 탐색하는 알고리즘이다.
핵심은 큐를 사용한다는 점이다
구현
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
2. 큐에서 시작(이전) 노드를 꺼내고, 시작 노드와 인접한 노드들을 큐에 넣고 방문 처리를 함.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
흐름을 이해하는데 도움을 주었던 위키피디아 gif를 첨부한다.
링크텍스트
파이썬을 이용하였는데, 파이썬에서 list로 큐를 구현하게 되면 list.pop() 연산이 시간적으로 매우 비효율적이라, deque 라이브러리를 사용하여 큐를 구현하였다.
import sys
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
방문 처리를 체크하는데에, bool타입의 visited[]를 생성하였다.
visited=[False]*11 #노드의 개수 +1개의 bool타입 리스트 생성
#방문 여부를 체크하기 위함
graph = [
[],
[2,5,9],
[1,3,4],
[2,4],
[3],
[1,6,8],
[5,7],
[6],
[5],
[1,10],
[9]
]
bfs(graph,1,visited)첨부한 gif를 python으로 구현한 main문이다.
필자는 graph를 구현하는데 2차원 리스트를 사용하였다. 파이썬의 경우 딕셔너리로도 구현이 가능하다.
1 2 3 4 5 6 7 8 9 10위의 코드를 실행하면 다음과 같은 결과가 나오고, 첨부한 gif를 같이 보면, 이해하는데 도움이 될 것이다.
앞장 DFS에 이어 다른 그래프 탐색 방식인 BFS를 구현, 설명 해보았다.
Q. 최단 경로를 구하는 문제는 두 알고리즘 중 뭘 사용하는 것이 좋을까?
정답은 BFS이다. 깊이 우선 탐색인 DFS는 가장 깊은 곳까지 탐색 후 다시 올라오는, 즉 시작 노드로부터 거리가 가장 멀리 떨어진 노드까지 탐색한 후에 다시 올라와서 다른 가지를 탐색하는 반면,
너비 우선 탐색인 BFS는 위에서 설명했듯이, 시작 노드로부터 같은 거리에 위치한 노드들 우선으로 탐색하기 때문에, 예를 들어 거리가 2인 위치가 목적지라고 가정하였을 때, BFS에선 거리가 3인 노드를 탐색하기 이전에 2인 노드들을 모두 탐색하기 때문에, 3인 노드까지 접근하지 않고도 최단 경로를 도출해낼 수 있다.
또 최단 경로를 구하는 다익스트라 알고리즘도 존재하는데, 이는 다음에 다뤄보도록 하자.
