[자료구조] BFS(Breadth First Search) Java 구현

BFS는 Breadth First Search로 

너비우선 탐색이란 뜻을 가진다.

 

너비 우선 탐색을 아래와 같은 과정으로 그래프를 모두 순회하는것이다.

자식노드와 그 형제노드를 모두 검색한뒤 그 다음에 있는 자식의 자식 노드와 그 형제들을 순회하는 방법이다.

 

 

해당 그림처럼 노드를 넓게 탐색한다. 그래서 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 

이방법을 사용한다.

 

BFS의 장점

 

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

2. 단순 검색 속도가 DFS보다 빠르다.

3. 너비를 우선 탐색하기 때문에 답이 되는 경로가 여러개인 경우 최단경로를 보장한다.

4. 최단 경로가 존재한다면 경로가 무한대로 깊어져도 최단경로를 반드시 찾을수 있다.

 

BFS의 단점

 

1. 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 노드를 저장해야해서 저장공간이 많이 필요하다.

2. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아져서 비현실적이다.

 

따라서 BFS는 가중치가 없는 그래프와 같은 곳에서는 특정 지점까지 가는 최단경로를 구할때

주로 쓰인다. 

ex) 미로

 

나는 BFS를 인접리스트와 인접행렬을 통해서 구현을 해봤다.

인접리스트와 인접행렬에 대해 잘 모르시는 분들은 아래 링크 참조하시면 될것 같다.

https://wpioneer.tistory.com/128

[자료구조] 인접리스트 구현 : LinkedList (Java)

https://wpioneer.tistory.com/129

[자료구조] 인접행렬로 구현한 그래프 (Java)

 

 

내가 BFS를 구현할 그래프는 아래와 같다.

 

소스를 한번 보도록하자.

 

Main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		Bfs bfs = new Bfs();
		int n = 9;
		
		AdjacencyList aj = new AdjacencyList(n);
		
		aj.addEdge(0, 1);
		aj.addEdge(1, 2);
		aj.addEdge(1, 3);
		aj.addEdge(2, 3);
		aj.addEdge(2, 4);
		aj.addEdge(3, 4);
		aj.addEdge(3, 5);
		aj.addEdge(5, 6);
		aj.addEdge(5, 7);
		aj.addEdge(6, 8);
		

		
		LinkedList<Integer>[] ll = aj.getAdj();
		int[] visit1 = new int[n];
		
		System.out.print("인접리스트로 구현 : ");
		bfs.bfsRoute1(3, visit1, ll);//인접 리스트로 BFS 구현
		
		System.out.println("\n--------------------------------");
		
		AdjMatrix am = new AdjMatrix(n);
		
		am.addEdge(0, 1);
		am.addEdge(1, 2);
		am.addEdge(1, 3);
		am.addEdge(2, 4);
		am.addEdge(2, 3);
		am.addEdge(3, 4);
		am.addEdge(3, 5);
		am.addEdge(5, 6);
		am.addEdge(5, 7);
		am.addEdge(6, 8);
		
		int[][] graph = am.getAdjGraph();
		int[] visit2 = new int[n];
		System.out.print("인접행렬로 구현 : "); //인접행렬로 BFS 구현
		bfs.bfsRoute2(3, visit2, graph);
	}

 Bfs Class

package co.kr.wook;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Bfs {
	//BFS는 너비우선 탐색이라서 형제 노드들을 모두방문한 다음에 다음 레벨로 넘어가서 보는것이다.
	
	public Bfs() {}
	
	public void bfsRoute1(int root, int[] visit, LinkedList<Integer>[] adjL) {
		LinkedList<Integer> al = adjL[root];
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(root); //시작 노드 queue에 삽입
		visit[root] = 1; //시작 노드 방문 처리
		
		while(queue.size()!=0) { //큐의 사이즈가 0보다 크다면 진입
			
			int v = queue.poll(); //큐에서 맨앞 값 빼기
			System.out.print(v+" ");
			al = adjL[v]; //해당 노드와 연결된 모든 인접노드 list 받기
			Iterator it = al.iterator();
			while(it.hasNext()) {
				int node = (int)it.next();
				if(visit[node]==0) { //방문 안되어 있는 노드는
					queue.add(node); //큐에 넣는다.
					visit[node] = 1;  // 큐에 넣은 노드는 방문처리를 해준다.
				}
					
			}			
		}
	}
	
	public void bfsRoute2(int root, int[] visit, int[][] adjM) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(root); //시작 노드 queue에 삽입
		visit[root] = 1; //시작 노드 방문 처리
		
		while(queue.size()!=0) { //큐의 사이즈가 0보다 크다면 진입
			
			int v = queue.poll();
			int[] am = adjM[v];
			System.out.print(v+" ");
			for(int i = 0;i<am.length;i++) {
				if(am[i] == 1 && visit[i] == 0) { //연결된 간선이고 방문하지 않은 노드일때 진입
					queue.add(i);//큐에 넣는다.
					visit[i] = 1;// 큐에 넣은 노드는 방문처리를 해준다.
				}
			}
		}
	}
}

 

BFS는 DFS와는 다르게 재귀호출 방식이 아닌 Queue를 활용해서 다음 노드를 집어 넣는방식이다.

 

그래서 처음에 시작 노드를 Queue에 넣고 해당 노드는 방문 처리를 해줘야 한다.

 

그리고 나서 그 노드와 인접한 노드들을 Queue에 모두 집어 넣은 다음 방문 처리를 해줘야 한다.

그래야지만 Queue에서 해당 노드를 꺼낼때 같은노드가 존재한다 하더라도 이미 방문 처리를 했기때문에

해당 노드는 Queue에 집어 넣지 않게 된다.

 

 

 

내가 만든 그래프의 BFS 결과는 아래와 같다.

 

시작노드가 0일때 결과

 

인접리스트로 구현 : 0 1 2 3 4 5 6 7 8 
--------------------------------
인접행렬로 구현 : 0 1 2 3 4 5 6 7 8 

 

시작 노드가 3일때 결과

 

인접리스트로 구현 : 3 1 2 4 5 0 6 7 8 
--------------------------------
인접행렬로 구현 : 3 1 2 4 5 0 6 7 8