BFS
너비 우선 탐색 = breadth-first search
그래프를 완전 탐색하는 방법 중 하나
시작 노드에서 출발해 시작 노드 기준으로 가까운 노드 먼저 방문하면서 탐색하는 알고리즘
즉, 깊게 탐색하기 전 넓게 탐색
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
특징
- FIFO : 선입선출
- Queue 자료구조 이용(구현도)
- 목표노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장
- 재귀적으로 동작하지 않는다
시간복잡도
(노드 수 : V, 에지 수 : E)
인접 리스트로 표현된 그래프: O(V+E)
인접 행렬로 표현된 그래프: O(V^2)
-> 이차원 배열일 경우, 결국 '행*열' 수
핵심 이론(원리)
-
BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화
시작 노드를 큐에 삽입하며 방문 배열 체크
-> 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요
-> 그래프 = 인접리스트로 표현
-> 탐색 = 큐 사용 -
큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입
인접 노드를 큐에 넣기 전, 방문배열을 체크하여 이미 방문한 노드는 큐에 삽입합지 않는다.
큐에서 꺼낸 노드는 탐색 순서에 기록 -
큐 자료구조에 값이 없을 때까지 반복
큐에 노드가 없을 때까지 앞선 과정 반복
선입 선출 방식 -> 탐색 순서가 DFS와 다름
사용에 적합한 문제
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
DFS, BFS 둘 다 상관없다.
2) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
구현
인접리스트로 구현
import java.util.*;
public class BFS_List {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
LinkedList<Integer>[] adjList = new LinkedList[n + 1];
for (int i = 0; i <= n; i++) {
adjList[i] = new LinkedList<Integer>();
}
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjList[v1].add(v2);
adjList[v2].add(v1);
}
for (int i = 1; i <= n; i++) {
Collections.sort(adjList[i]); // 방문 순서를 위해 오름차순 정렬
}
System.out.println("BFS - 인접리스트");
bfs_list(v, adjList, visited);
}
// BFS - 인접리스트
public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
Queue<Integer> queue = new LinkedList<Integer>();
visited[v] = true;
queue.add(v);
while(queue.size() != 0) {
v = queue.poll();
System.out.print(v + " ");
Iterator<Integer> iter = adjList[v].listIterator();
while(iter.hasNext()) {
int w = iter.next();
if(!visited[w]) {
visited[w] = true;
queue.add(w);
}
}
}
}
}인접행렬로 구현
import java.util.*;
public class BFS_Array {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
int[][] adjArray = new int[n+1][n+1];
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for(int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjArray[v1][v2] = 1;
adjArray[v2][v1] = 1;
}
System.out.println("BFS - 인접행렬");
bfs_array(v, adjArray, visited);
}
// BFS - 인접행렬
public static void bfs_array(int v, int[][] adjArray, boolean[] visited) {
Queue<Integer> q = new LinkedList<>();
int n = adjArray.length - 1;
q.add(v);
visited[v] = true;
while (!q.isEmpty()) {
v = q.poll();
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (adjArray[v][i] == 1 && !visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
}