[알고리즘] 너비 우선 탐색(BFS) - JAVA(자바)

너비 우선 탐색(Breadth-First Search) - 노드 수가 적고 최단 경로를 찾을 때 유리함

• 그래프의 시작 노드나 임의의 노드에서 시작해 가장 가까운 노드 부터 방문하면서 탐색하는 기법으로 그래프 완전 탐색 방법이다.
  • BFS를 시작할 노드를 정한다.
  • 시작노드와 가까운 노드부터 방문여부를 체크하며 방문한다.
    • 가까운 노드를 먼저 탐색 -> dfs와 목표를 찾는 경로가 다수일 때, 최단 경로로 찾는다.
  • 가장 가까운 노드들을 다 방문했다면 다음 깊이로 넘어가서 탐색한다.  
  • 모든 노드를 방문할 때까지 반복한다. *한번 방문한 노드는 재방문하지 않는다.
• 선입선출방식인 큐를 사용해서 구현한다.
• 시간복잡도
  • 그래프를 인접리스트로 표현할 경우 O(V+E)이 된다. V: 정점(vertex) 수(=노드 수)  E: 간선(edge) 수
  • 그래프를 인접행렬로 표현할 경우 O(V²)이 된다.
• 모든 노드를 방문해야 할 때, 사용한다.
• 장점
  • dfs와 목표를 찾는 경로가 다수일 때, 최단 경로를 보장한다. ->최단거리찾기의 경우 bfs 유리하다.
  • 최단 경로가 존재한다면 경로의 깊이가 무한하게 깊어지더라도 해를 찾을 수 있다. 
  • 노드 수가 적고 깊이가 얕은 경우에 유리하다.
• 단점
  
  • 탐색할 경로가 많아진다면 bfs는 큐를 사용해서 다음 방문할 노드 저장 -> 저장공간이 dfs에 비해 더 많이 필요하다.

 

예를 들어 다음과 같은 그래프를 노드를 방문한 순서대로 숫자를 적으면 아래와 같이 된다.

시작 노드와 가장 인접한 노드를 왼쪽부터 방문한다. (가로 줄)

방문하지 않은 노드가 없다면 다음 깊이로 넘어가서 방문한다.

위에 그림을 보면 1번 노드에서 시작할 때, 2,3,4를 방문하고 5,6,7,8을 방문했다는 것을 알 수 있다.

 

 

 

[구현코드 - JAVA]

위에 있는 그림의 그래프 노드간의 연결관계를 인접리스트로 저장

import java.util.*;

public class Main {
	public static ArrayList<Integer>[] arrayList = new ArrayList[10]; //그래프를 표현할 인접리스트
	public static boolean[] visited = new boolean[10]; //방문체크할 배열
	
	public static void main(String[] args){
		
		//인접리스트의 ArrayList 각각 생성 및 초기화
		for(int i=0; i<10; i++) {
			arrayList[i] = new ArrayList<Integer>(); 
		}
		
		//양방향으로 연결되어 있으므로 노드 정보 양쪽 모두 저장
		arrayList[1].add(2);
		arrayList[1].add(3);
		arrayList[1].add(4);
		arrayList[2].add(1);
		arrayList[3].add(1);
		arrayList[4].add(1);
		
		arrayList[2].add(5);
		arrayList[2].add(6);
		arrayList[5].add(2);
		arrayList[6].add(2);
		
		arrayList[3].add(7);
		arrayList[7].add(3);
		
		arrayList[4].add(8);
		arrayList[8].add(4);
		
		arrayList[8].add(9);
		arrayList[9].add(8);
		
		bfs(1); //1번 노드부터 시작
		
	}
	
    //너비우선탐색
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<>();
		visited[start] = true; //방문표시
		queue.add(start); //시작노드 큐에 삽입
		
		
		//큐가 빌 때까지
		while(!queue.isEmpty()) {
			//현재 노드 - 큐에 있는 노드중 가장 먼저 들어가있는 노드 
			int now = queue.poll();
			
			System.out.print(now+" "); //현재 노드 출력
			
			//현재 노드의 인접한 노드 방문체크
			for(int n : arrayList[now]) {
				//방문하지 않은 인접노드라면
				if(!visited[n]) {
					queue.add(n); //방문하지 않은 인접노드 큐에 삽입
					visited[n] = true; //노드 방문표시
				}
				System.out.println(now+"인접한 노드 "+n);
			}
			
		}
	}
}

//결과
// 1 2 3 4 5 6 7 8 9

위 코드 과정을 설명하면 다음과 같다.

처음에 큐에 1이 삽입하고, poll()를 사용해 큐에서 제거하고 값을 가져온다. - now: 1

1과 인접한 노드는 2,3,4로 차례대로 방문표시를 하고 큐에 삽입한다. 큐: 2,3,4

for문이 끝나고 다시 poll()을 해 큐에 남아있는 수 중 가장 먼저 삽입되었던 2를 제거하고 값을 가져온다. - now: 2, 큐: 3,4

2와 인접한 노드는 5,6으로 차례대로 방문표시를 하고 큐에 삽입한다. 큐: 3,4,5,6

for문이 끝나고 다시 poll()을 해 3을 제거하고 값을 가져온다. - now: 3, 큐: 4,5,6

이 과정을 반복하며 그래프를 탐색한다.