[BFS] BFS의 설명과 간단한 예제풀이

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

1. 특징

1. BFS는 재귀적으로 동작하지 않는다.

2. 이 알고리즘도 DFS와 마찬가지로 그래프 탐색의 경우 방문한 노드에 대해 기존에 방문했었는지의 여부를 검사를 해야 무한루프에 빠지지 않는다.

3. BFS는 방문한 노드들을 차례대로 저장한 후 먼저 방문한 노드부터 먼저 꺼낼 수 있는 자료구조인 큐를 사용합니다. (선입선출이 원칙!!)

4. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A사람과 B사람에 존재하는 관계 경로를 찾을려면

DFS는 모든 친구 관계를 다 살펴봐야 할수도있는데 BFS는 A와 가까운 관계부터 먼저 탐색함에 따라 DFS보다 검색속도가 빠르다.

 

BFS를 Java로 직접 구현해보자

2. BFS - 큐

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

public class Main {

	static final int MAX_N = 10;
	static int N, E;

	static int[][] graph = new int[MAX_N][MAX_N];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		E = sc.nextInt();

		for (int i = 0; i < N; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			graph[u][v] = graph[v][u] = 1;
		}
		dfs(0);
	}

	public static void dfs(int nodeIdx) {
		boolean[] visited = new boolean[MAX_N];
		Queue<Integer> queue = new LinkedList<>();
		visited[nodeIdx] = true;
		queue.add(nodeIdx);

		while (!queue.isEmpty()) {
			int curr = queue.remove();

			System.out.println(curr + "다음 노드는 ");

			for (int next = 0; next < N; next++) {
				if (!visited[next] && graph[curr][next] != 0) {
					visited[next] = true;
					queue.add(next);
					
				}
			}

		}

	}
}