BFS (Breadth-First Search) 알고리즘 정리

저번 포스팅에서 내가 DFS 에 대하 포스팅을 했었다.

 

DFS 알고리즘이 경우의수를 찾기 위해 사용하는 알고리즘이라면,

BFS 알고리즘은 최단 거리를 찾기 위해 사용하는 알고리즘이라고 생각하면 좋을 것 같다.

 

먼저 코드를 보여드리겠다.

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

public class BFS {
	public static void main(String args[]) {
		BFS tree = new BFS();
		Node root = new Node(1);
		root.lt = new Node(2);
		root.rt = new Node(3);
		root.lt.lt =new Node(4);
		root.lt.rt = new Node(5);
		root.rt.lt = new Node(6);
		root.rt.rt = new Node(7);
		tree.bfs(root);
	}

	public void bfs(Node root) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int i=0; i<size; i++) {
				Node curNode = queue.poll();
				System.out.print(curNode.data+ " ");
				if(curNode.lt != null) queue.offer(curNode.lt);
				if(curNode.rt != null) queue.offer(curNode.rt);
			}
		}
	}
}

class Node {
	int data;
	Node lt;
	Node rt;

	public Node(int data) {
		this.data = data;
		this.lt = null;
		this.rt = null;
	}
}

main에서 그려진 그래프는 아래와 같다.

queue를 이용하는데 개념은 간단하다.

먼저 탐색하고자하는 노드에 오면 data값을 queue에서 꺼내 출력하고, 그리고 queue에다 연결된 lt, rt 위치의 노드를 queue에 넣는다. 아래의 그림을 보면 쉽게 이해 될 것이다.

 

 

위의 그림처럼 1을 넣고 꺼내면서 출력하면서... 1에 연결된 2 와 3을 queue에 밀어넣는다.

그리고 순차적으로 꺼내서 출력하면서 연결된것들을 계속 넣어준다 .. 4나 5는 연결된게 없으니 queue에 더이상 값이 들어가지 않는 것을 확인할 수 있다. 이렇게하면 간단하게 1 2 3 4 5 6 7 이렇게 넓이 우선 탐색이 가능하게 된다.

 

끝.