728x90
참고: https://blog.naver.com/ndb796/221230944971
너비 우선 탐색 (BFS)은 탐색을 할 때, 너비를 우선으로 하여 탐색을 수행하는 알고리즘이다. 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법이다. 너비 우선 탐색은 최단경로를 찾아준다는 점에서 최단길이를 보장해야 할 때 많이 사용한다. (DFS가 스택을 사용했다면, BFS는 큐(Queue)를 이용한다.
* 너비 우선 탐색이란 ?
루트노드(또는 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회방법
- 즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것
- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
- 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다
* 특징
- 직관적이지 않다 -> 너비 우선 탐색(BFS)은 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다
- 너비 우선 탐색(BFS)은 재귀적으로 동작하지 않는다
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 -> 이를 검사하지 않으면 무한루프에 빠질 수 있다
- BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다
-> 즉, 선입선출(FIFO) 원칙으로 탐색
-> 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다
* 너비 우선 탐색(BFS)의 시간 복잡도
- 인접 리스트로 표현된 그래프: O(N + E)
- 인접 행렬로 표현된 그래프: O(N^2)
- 깊이 우선 탐색(DFS)와 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우
인접 행렬보다 인접 리스트를 사용하는 것이 좋다
* BFS 구현 알고리즘
package queue;
import java.util.Iterator;
import java.util.LinkedList;
//인접 리스트를 이용한 방향성 있는 그래프 클래스
public class Graph {
private int v; //노드의 개수
private LinkedList<Integer> adj[]; //인접 리스트
//생성자
Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i = 0; i < v; i++) //인접 리스트 초기화
adj[i] = new LinkedList();
}
// 노드를 연결 v -> w
void addEdge(int v, int w) {
adj[v].add(w);
}
// s를 시작 노드 한 BFS로 탐색하면서 탐색한 노드들을 출력
void BFS(int s) {
// 노드의 방문 여부 판단 (초기값: false)
boolean visted[] = new boolean[v];
// BFS 구현을 위한 큐(Queue) 생성
LinkedList<Integer> queue = new LinkedList<>();
// 현재 노드를 방문한 것으로 표시하고 큐에 삽입(enqueue)
visted[s] = true;
queue.add(s);
// 큐(Queue)가 빌 때 까지 반복
while (queue.size() != 0) {
// 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
s = queue.poll();
System.out.print(s + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
if (!visted[n]) {
visted[n] = true;
queue.add(n);
}
}
}
}
}
//사용방법 --> Graph 클래스 객체 사용
public static void main(String[] args) {
Graph g = new Graph(4);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,2);
g.addEdge(2,0);
g.addEdge(2,3);
g.addEdge(3,3);
g.BFS(2); //주어진 노드를 시작 노드로 BFS 탐색
}
728x90
'알고리즘' 카테고리의 다른 글
Do it! 자료구조와 함께 배우는 알고리즘 입문 - 재귀 알고리즘 (0) | 2019.12.29 |
---|---|
Do it! 자료구조와 함께 배우는 알고리즘 입문 - 검색 (0) | 2019.12.18 |
[알고리즘] GCD 최대공약수, LCM 최소공배수 (0) | 2019.11.24 |
[알고리즘] 순열(Permutation) (0) | 2019.10.12 |
[알고리즘] 깊이 우선 탐색 ( DFS, Depth-First Search) (0) | 2019.10.09 |