[JAVA] 너비 우선 탐색 BFS(Breadth-first search)

 

동작방식

하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

 

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

시간복잡도

DFS 시간복잡도와 동일함

- 인접리스트 : O(|V| + |E|) (정점의 개수:V, 간선의 개수:E)

- 인접행렬 : O(V^2) (정점의 개수:V)

참고사이트

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

기본코드

입력값

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

코드

package study.graph;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BFS {

	static int[] used;
	static int[][] map;
	static int N, M;
	public static void main(String[] args) throws IOException{
		
		System.setIn(new FileInputStream("input\\bfs.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		used = new int[N+1];
		map = new int[N+1][N+1]; // 인접행렬을 이용하기 위한 2차원 배열 생성
		
		StringTokenizer st = null;
		for(int m=0; m<M; m++) {
			st = new  StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
			map[b][a] = 1; //양방향이기 때문에..
		}
		
		System.out.print("그래프 BFS 방문 순서 : " );
		bfs(1);
		
		bw.close();
		br.close();
	}
	
	static void bfs(int st) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(st);
		used[st] = 1; //방문표시
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.print( x + " ");
			
			for(int i=1; i<=N; i++) {
				if(map[x][i] == 1 && used[i] == 0) {
					// 다음 노드와 연결되어 있고 아직 방문하지 않았으면 q에 넣음
					q.add(i);
					used[i] = 1;//방문 표시
				}
			}
		}
	}
}