[그래프 알고리즘]BFS 너비 우선 탐색

Breadth First Search

그래프를 탐색할 때 너비를 우선해서 탐색한다는 것은, 현재 정점에서 인접해 있는 노드들을 우선으로 방문한다는 뜻입니다.

다음으로 방문할 노드를 선택할 때, 최근에 방문한 노드를 기준으로 삼는 DFS와는 달리 BFS는 먼저 방문한 노드를 기준으로 삼습니다.

따라서 방문할 노드를 기록하고, 다음 방문할 노드를 정할 때, 가장 먼저 기록된 노드를 방문하면 됩니다.

한 노드에서 가까운 노드를 먼저 방문한다는 성질 덕분에, BFS는 그래프에서의 최단 경로 찾기에 자주 이용됩니다.

대표적인 최단 경로 찾기 알고리즘인 다익스트라 알고리즘은 BFS를 응용합니다.

 

큐로 구현

방문할 노드를 리스트에 넣고, 리스트에서 가장 먼저 들어간 노드를 방문해야하기 때문에, FIFO(First In First Out)성질을 만족하는 큐를 이용하는 것이 적절합니다. DFS를 스택으로 구현한 코드에서 스택을 큐로 바꾸면 BFS 구현이 됩니다.