BFS 개념

BFS

: 너비 우선 탐색

• 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 보통 그래프 탐색에 사용
• 두 노드 사이의 최단 경로 또는 임의의 경로를 찾을 때 사용
• Queue로 구현

 

BFS의 특징

• BFS는 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다.
  • 거리 1부터 2, 3 순서대로
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
  • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 재귀적으로 동작하지 않는다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  • 선입선출(FIFO) 원칙으로 탐색
• 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

 

 

 

시작 노드: 1

 

BFS 탐색 과정

 

1. 큐에 1번 노드를 넣고 방문 했음을 표시한다.

2. 1번과 인접한 노드들 2, 3, 7을 큐에 넣고 방문 처리한다.

3. 큐에서 노드 하나를 꺼낸다. 큐는 FIFO기 때문에 1번 노드를 꺼낸다.

4. 인접한 노드가 없다면 3. 과정으로 돌아간다.

5. 인접한 노드가 있고 방문하지 않았다면 큐에 넣고 방문 처리 후 3. 과정으로 돌아간다.

6. 큐가 빌 때까지 반복한다.

 

 

BFS 탐색 순서

1 -> 2 -> 3 -> 7 -> 5 -> 6 -> 4 -> 8

 

 

BFS 구현

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

public class Main {
	
	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를 시작 할 노드 번호 offer()
		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://velog.io/@ygy0102/Java-BFS-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-%EA%B5%AC%ED%98%84-%EC%9E%90%EB%B0%94-Java

[Java] BFS - 너비 우선 탐색 구현 (자바 | Java)

https://codingnojam.tistory.com/41

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

https://minhamina.tistory.com/36

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