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

BFS

BFS는 Breadth-First Search, 너비 우선 탐색이라고도 부르며,

그래프에서 가까운 노드부터 탐색하는 알고리즘 입니다.

 

DFS는 스택을 이용하여 구현을 하였다면,

BFS는 선입선출(FIFO, First In First Out) 방식인 큐(Queue) 자료구조를 사용합니다.

BFS는 일반적으로 DFS보다 실제 수행 시간은 좋은 편입니다.

 

알고리즘의 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 하고 방문 처리를 합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

 

 

그림 1 : 시작 노드인 1을 큐에 삽입하고 방문처리를 하였습니다.

           방문 처리된 노드는 회색, 큐에서 꺼낸 노드는 노란색으로 표현하였습니다.

 

그림 2 : 큐에서 노드 1을 꺼내고 방문하지 않은 인접 노드 2, 3, 8을 모두 큐에 삽입하고, 방문처리를 하였습니다.

           ( ※ 작은 순대로 삽입 )

 

그림 3 : 큐에서 노드 2를 꺼내고 방문하지 않은 인접 노드 7을 큐에 삽입하고 방문 처리를 하였습니다.

 

그림 4 : 큐에서 노드 3을 꺼내고 방문하지 않은 인접 노드 4, 5 를 큐에 삽입 하고 방문 처리를 하였습니다.

 

그림 5 : 큐에서 노드 8을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시합니다.

 

그림 6 : 큐에서 노드 7을 꺼내고 방문하지 않은 인접 노드인 7을 큐에 삽입하고 방문 처리를 하였습니다.

 

남아 있는 노드에 방문하지 않은 인접 노드가 없습니다. 따라서 모든 노드를 차례대로 꺼냅니다.

 

노드의 탐색순서는 다음과 같습니다.

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

 

 

 

BFS구현 방법

 

인접 행렬로 구현하기

전체 소스 코드

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

public class BFSQueue {
	
	public static void bfs(int v, int[][]arr, boolean[]visit) {//시작할 노드 번호, 그래프, 방문 여부
		int n = arr.length-1; //노드 개수
		Queue<Integer> qu = new LinkedList<>();  ///Queue는 인터페이스로서 구현객체인 LinkedList를 사용해야한다.
		
		qu.add(v);
		visit[v]=true;
		
		while(!qu.isEmpty()) {
			v= qu.poll();
			System.out.print(v+" ");
		
			for(int i=1;i<=n;i++) {  ///노드는 1부터 n까지
				if(!visit[i]&&arr[v][i]==1) {
					qu.add(i);
					visit[i]=true;
				}
			}
		}
	
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); //정점 수
		int E = sc.nextInt(); //간선 수
		
		
		boolean[] visit = new boolean[V+1]; //방문 여부를 검사할 배열 
		
		int[][] arr = new int[V+1][V+1];

		// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
		// 입력으로 주어지는 간선은 양방향이다.
		for(int i = 0; i < E; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();

			arr[v1][v2] = 1;
			arr[v2][v1] = 1;
		}
		
		
		bfs(1,arr,visit);
		
		
	}
}

입 출력

 

---

이상으로 BFS를 알아보았습니다.