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

개념

- 특정 노드에서 부터 가장 가까운 노드를 우선적으로 탐색하는 알고리즘.

- 탐색중인 정점의 연결된 노드에 방문한 적이 없다면 해당 노드를 큐에 삽입하고 방문 이력을 저장한다.

- 즉, 큐에서 값을 하나 꺼내고 그 값과 연결된 모든 노드를 방문하여 큐에 삽입하는 과정을 반복한다.

탐색 그래프

그래프 표현 - 인접행렬

	static boolean[] check;
	static int[][] map;

	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.println(x);
			for (int i = 0; i < map[x].length; i++) {
				//현재 노드와 연결된 간선이 존재하는지 확인
				int y = map[x][i];
				//연결된 간선이 존재하고, 현재 그 노드가 방문을 한 상태가 아니면 큐에 담고 방문처리
				if(map[x][i] == 1 && !check[i] ) {
			 		q.offer(i);
			  		check[i] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		int[][] edgeArr = {
							{1,2}
							,{1,3}
							,{2,3}
							,{2,4}
							,{3,5}
						  };
		
		map = new int[6][6];
		check = new boolean[6];
		
		//간선 설정
		for (int i = 0; i < edgeArr.length; i++) {
			int temp1 = edgeArr[i][0];
			int temp2 = edgeArr[i][1];
			map[temp1][temp2] = map[temp2][temp1] = 1; 
		}
		bfs(1);
		
	}

 

※ 장점

- 모든 간선의 가중치가 동일할 경우 출발노드에서 목표노드까지의 최단 길이 경로를 보장할 수 있다.

 (예) 미로찾기

 

※ 단점

- 노드의 수가 많을수록 많은 저장공간이 필요하다. (최악의 경우 거의 모든 노드에 대한 저장공간이 필요)

- 목표 노드가 깊은 단계에 있을 경우 오랜 시간이 소요된다.