[알고리즘] 너비 우선 탐색 (Breath First Search, BFS) - JAVA / 자바

너비 우선 탐색(Breath First Search, BFS)

  : 하나의 정점으로부터 시작하여 인접한 정점들을 우선으로 탐색하여 최종적으로 모든 정점을 탐색하는 방법

 

특징

  ① 목표 지점까지 최단 길이(경로)를 보장한다.

  ② 경로가 길수록 인접한 정점이 많이 생겨나므로(저장되므로) 저장 공간이 많이 필요하다.

  ③ 선입선출(FIFO, First In First Out) 구조이다.

---

BFS 알고리즘

① 시작 정점 v를 결정하여 방문
② 정점 v에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue
③ 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점을 다시 차례로 방문하기 위해 큐에서 deQueue 하여 구한 정점에서 ②반복
④ 큐가 공백이 될 때까지 ②~③반복

답 >>>

A - B - C - D - E - G - F

---

의사 코드(Pseudo code)

BFS(v)
    for (i ← 0; i<n; i ← i+1) do {
        visited[i] ← false;
    }
    Q ← createQueue();
    visited[v] ← true;
    v 방문;
    while (not isEmpty(Q)) do {
        while (visited[v의 인접정점 w] = false) do {
            visited[w] ← true;
            w 방문;
            enQueue(Q, w);
        }
        v ← deQueue(Q);
    }
end BFS()

---

Java 코드 구현

public static String bfs(int v, boolean node[][]) {
	StringBuilder sb = new StringBuilder();
	Queue<Integer> queue = new LinkedList<>();
	boolean visited[] = new boolean[n+1];
	queue.add(v);
	visited[v] = true;
	int idx;
	while(!queue.isEmpty()) {
		idx = queue.remove();
		sb.append(idx+" ");
		for(int i=1; i<node.length; i++) 
			if(node[idx][i] && !visited[i]) {
				queue.add(i);
				visited[i] = true;
			}
	}
	return sb.toString();
}

시간 복잡도

 - 인접 리스트 = O(N+E)

 - 인접 행렬 = O(N^2)

* N = 정점의 수, E = 간선(노드)의 수

---

대표적인 BFS 사용 예

 - 최단 경로 탐색

 - 그래프 사이클 찾기

 - 그래프 연결 요소 찾기

 - 그 외...