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

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.

시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.

이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다.

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS의 특징

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

BFS의 수행 과정

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
   • 큐에 방문된 노드를 삽입(enqueue)한다.
   • 초기 상태의 큐에는 시작 노드만이 저장
2. 큐에서 꺼낸 노드과 인접한 노드들을 큐에 추가한다. (모두 차례로 방문)
   • 큐에서 꺼낸 노드를 방문한다.
   • 큐에서 꺼낸 노드과 인접한 노드들을 모두 방문한다.
   • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
   • 큐에 방문된 노드를 삽입(enqueue)한다.
3. 큐가 공백 상태가 될 때까지 계속한다.

BFS 구현 방법

큐(Queue)를 이용

그래프 표현하기

정점의 개수, 간선의 개수, 탐색을 시작할 정점을 번호를 입력받는다.

노드 방문 여부를 검사하기 위한 boolean 배열도 선언한다.

Scanner sc = new Scanner(System.in);

int n = sc.nextInt(); // 정점의 개수 
int m = sc.nextInt(); // 간선의 개수 
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

1. BFS 인접 리스트로 구현

LinkedList<Integer>[] adjList = new LinkedList[n + 1];

for (int i = 0; i <= n; i++) {
	adjList[i] = new LinkedList<Integer>();
}

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

for (int i = 1; i <= n; i++) { 
	Collections.sort(adjList[i]); // 방문 순서를 위해 오름차순 정렬 
}

System.out.println("BFS - 인접리스트");
bfs_list(v, adjList, visited);

처음 BFS 함수를 호출하면 int v에 탐색을 시작할 정점의 번호가 들어있고, 이 시작 정점부터 탐색을 시작한다.

큐를 생성하고 시작 정점 v의 값을 큐에 넣는다.

1. 큐의 front에 있는 정점을 꺼낸다(poll), 이를 기준으로 간선이 연결되어 있고(인접하고), 아직 방문되지 않은 정점을 찾는다.
2. 조건에 맞는 정점을 찾는다면 해당 정점을 방문했음으로 표시 후, 큐에 넣는다.
   큐가 소진될 때까지 이를 반복하며 BFS를 수행하는 것이다.

public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
	Queue<Integer> queue = new LinkedList<Integer>();
	visited[v] = true; 
	queue.add(v);

	while(queue.size() != 0) { 
		v = queue.poll(); 
		System.out.print(v + " ");

		Iterator<Integer> iter = adjList[v].listIterator();
		while(iter.hasNext()) { 
			int w = iter.next(); 
			if(!visited[w]) { 
				visited[w] = true; 
				queue.add(w); 
			} 
		}
	}
}

2. BFS 인접 행렬로 구현

int[][] adjArray = new int[n+1][n+1];

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

	adjArray[v1][v2] = 1;
	adjArray[v2][v1] = 1;
}

System.out.println("BFS - 인접행렬");
bfs_array(v, adjArray, visited);

public static void bfs_array(int v, int[][] adjArray, boolean[] visited) {
	Queue<Integer> q = new LinkedList<>();
	int n = adjArray.length - 1;

	q.add(v);
	visited[v] = true;

	while (!q.isEmpty()) {
		v = q.poll();
		System.out.print(v + " ");

		for (int i = 1; i <= n; i++) {
			if (adjArray[v][i] == 1 && !visited[i]) {
				q.add(i);
				visited[i] = true;
			}
		}
	}
}

전체 코드
1. 인접 리스트로 구현한 BFS

import java.util.*;

public class BFS_List {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

		boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

		LinkedList<Integer>[] adjList = new LinkedList[n + 1];

		for (int i = 0; i <= n; i++) {
			adjList[i] = new LinkedList<Integer>();
		}

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

		for (int i = 1; i <= n; i++) { 
			Collections.sort(adjList[i]); // 방문 순서를 위해 오름차순 정렬 
		}

		System.out.println("BFS - 인접리스트");
		bfs_list(v, adjList, visited);
	}

	// BFS - 인접리스트 
	public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited[v] = true; 
		queue.add(v);

		while(queue.size() != 0) { 
			v = queue.poll(); 
			System.out.print(v + " ");

			Iterator<Integer> iter = adjList[v].listIterator();
			while(iter.hasNext()) { 
				int w = iter.next(); 
				if(!visited[w]) { 
					visited[w] = true; 
					queue.add(w); 
				} 
			}
		}
	}

}

입력

5 5 3
5 4
5 2
1 2
3 4
3 1

출력

BFS - 인접리스트
3 1 4 2 5 

2. 인접 행렬로 구현한 BFS

import java.util.*;

public class BFS_Array {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); // 정점의 개수 
		int m = sc.nextInt(); // 간선의 개수 
		int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 

		boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열 

		int[][] adjArray = new int[n+1][n+1];

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

			adjArray[v1][v2] = 1;
			adjArray[v2][v1] = 1;
		}

		System.out.println("BFS - 인접행렬");
		bfs_array(v, adjArray, visited);
	}
	
	// BFS - 인접행렬
	public static void bfs_array(int v, int[][] adjArray, boolean[] visited) {
		Queue<Integer> q = new LinkedList<>();
		int n = adjArray.length - 1;

		q.add(v);
		visited[v] = true;

		while (!q.isEmpty()) {
			v = q.poll();
			System.out.print(v + " ");

			for (int i = 1; i <= n; i++) {
				if (adjArray[v][i] == 1 && !visited[i]) {
					q.add(i);
					visited[i] = true;
				}
			}
		}
	}
	
}

입력

4 5 1 3
1 2
1 3
1 4
2 4
3 4

출력

BFS - 인접행렬
1 2 3 4 

BFS 시간복잡도

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우

• 그래프가 인접 리스트로 표현된 경우 O(n+e)
• 인접 행렬로 표현된 경우 O(n^2)이다.

희소 그래프인 경우 인접 리스트의 사용이 인접 행렬보다 유리

(희소 그래프는 그래프 내에 적은 수의 간선을 가지는 그래프로 인접 행렬을 사용하면 메모리의 낭비가 크기 때문)

연습문제
백준 1260번 : DFS와 BFS

출처: https://minhamina.tistory.com/m/36