BFS 너비 우선 탐색

BFS (Breadth Fisrt Search)

• 너비 우선 탐색 이라고 부른다.
• 가까운 노드부터 우선적으로 탐색하기 때문에 넓게 탐색해서 너비 우선 탐색이다.
• Queue 자료구조를 사용하여 구현할 수 있다.

탐색 방식

• 루트 노드 (혹은 다른 임의의 노드) 에서 시작하여 인접한 노드를 먼저 탐색한다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  • ex) 미로 탐색 (최단 거리)

특징

• 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1 탐색 후, 2,3,4 순서로 탐색)
• 그래프 탐색의 경우, 어떤 노드를 방문했었는지의 여부를 반드시 검사해야한다. 그래서 노드를 큐에 담을 때에는 꼭 방문처리를 한 후에 담는다. 방문 여부를 체크하지 않으면 무한루프에 빠질 수 있다. (이미 방문한 노드를 계속 큐에 넣을 수 있기 때문)
• 그렇기 때문에 BFS는 재귀적으로 동작하지 않는다.
• 일반적으로 큐를 이용하여 반복적 형태로 구현하는 것이 가장 잘 동작한다.
• 가까운 노드를 방문하여 차례로 저장하여 꺼낼 수 있도록 Queue 자료구조를 사용한다. 이를 통해 선입선출 방식으로 탐색할 수 있게 된다.

 

 

그래프

1번 노드부터 BFS 탐색을 하면 1->2->3->8->6->5->4->7 순서로 탐색이 된다.

탐색의 순서는 아래와 같다.

 

1. 큐에 1번 노드(시작노드)을 넣고 방문처리 한다. (큐에 넣으려면 '반드시' 방문처리를 한다.)
2. 큐에 있는 1번 노드를 꺼내서 1번 노드와 연결된 노드들을 체크한다.
   1. 이미 방문했다 -> pass 
   2. 방문하지 않았다 -> 방문 표시 하고, 큐에 넣는다.
3. 큐에 담긴 다른 노드도 꺼내서, 2번을 반복한다.
4. 큐가 끝날 때까지 반복해주면 끝

 

위의 그래프를 통해 실제 java 코드로는 어떻게 구현될까? 

import java.util.LinkedList;
import java.util.Queue;

public class StudyBFS {
	
	public static void main(String[] args) {
		
		// 그래프를 2차원 배열로 표현해줍니다.
		// 배열의 인덱스를 노드와 매칭시켜서 사용하기 위해 인덱스 0은 아무것도 저장하지 않습니다.
		// 1번인덱스는 1번노드를 뜻하고 노드의 배열의 값은 연결된 노드들입니다.
		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));
		//출력 내용 : 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 -> 
	}
	
	static String bfs(int start, int[][] graph, boolean[] visited) {
		// 탐색 순서를 출력하기 위한 용도
		StringBuilder sb = new StringBuilder();
		// BFS에 사용할 큐를 생성해줍니다.
		Queue<Integer> q = new LinkedList<Integer>();
		 
		// 큐에 BFS를 시작 할 노드 번호를 넣어줍니다.
		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() ;
	}
}

 

---

출처

https://codingnojam.tistory.com/41

[Algorithm] BFS(Breadth-first search)를 Java로 구현해보자!

https://minhamina.tistory.com/36

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현