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

너비 우선 탐색 ( Breadth-first search )

---

트리나 그래프를 방문 또는 탐색하는 방법으로 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법.

 

출처 : http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

 

탐색 방법

1. 루트노드에서 시작한다.

 

 

2. 자식노드들을 저장한다.

 

 

3. 저장되어있는 노드를 방문하며 저장되어있는 노드들의 자식들을 저장하며

 

 

4. 위의 과정을 모든 노드를 방문할 때 까지 반복하며 완료 시 탐색을 종료한다.

 

 

 

특징

1. 어떤 노드를 방문했는지 반드시 검사 해야 한다.

2. Queue를 사용하는 경우가 일반적이며 재귀적으로 동작하지 않는다.

3. Prim, Dijkstra알고리즘과 유사하다.

 

 

장점

1. 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.

2. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.
3. 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
4. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다.

 

단점

1. 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다.

 

 

인접 리스트로 구현한 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); 
				} 
			}
		}
	}

}

 

 

 

인접 행렬로 구현한 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;
				}
			}
		}
	}
	
}

 

 

https://minhamina.tistory.com/36