너비우선탐색이라고도 불린다. 그래프를 깊게보다는 가까운 노드부터 넓게 탐색하는 알고리즘이다.
BFS의 탐색 순서는 다음과 같다.
BFS는 큐 자료구조를 이용해 데이터에 접근하며, 시간복잡도는 O(N)이 소요된다. BFS가 DFS보다 구현이 좀더 빠르게 동작한다.
주로 두 노드 사이의 최단경로, 혹은 임의의 경로를 찾고 싶을때 사용되는 알고리즘이다. DFS와 다르게 재귀적으로 동작하지 않는다.
다만 그래프 탐색시 어떤 노드를 방문했었는지를 반드시 체크해야한다. 그렇지 않으면 무한루프에 빠지게 된다.
package DFS_BFS;
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
public static void main(String[] args) {
// 그래프의 연결상태를 2차원 배열로 표현
// 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
// 방문처리를 위한 boolean 배열 선언
boolean[] visited = new boolean[9];
System.out.println(bfs(1, graph, visited));
}
static String bfs(int start, int[][] graph, boolean[] visited) {
// 탐색순서 출력용 스트링빌더
StringBuilder sb = new StringBuilder();
// 노드 탐색을 위한 큐
Queue<Integer> q = new LinkedList<Integer>();
// 시작노드 삽입 및 방문처리
q.offer(start);
visited[start] = true;
// 큐에 데이터가 없을때까지 반복
while(!q.isEmpty()) {
// 큐에서 노드 꺼냄
int nodeIndex = q.poll();
sb.append(nodeIndex + " -> ");
// 꺼낸 노드와 인접한 노드 순회
for(int i = 0; i < graph[nodeIndex].length; i++) {
int temp = graph[nodeIndex][i];
// 방문처리 안된노드는 방문처리후 큐에 넣기
if(!visited[temp]) {
visited[temp] = true;
q.offer(temp);
}
}
}
return sb.toString();
}
}
참고자료
나동빈, 「이것이 코딩테스트다」
소스코드 : [Algorithm] BFS (Depth-first Search)를 Java로 구현해보자!