BFS

Breadth First Search. 흔히 줄여서 BFS로 쓴다.
한국어 표기는 너비 우선 탐색.

• DFS의 경우에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.
• BFS는 가중치가 없는 그래프에서는 시작점에서 끝점까지의 최단 경로를 알아낼 수 있다.
• 따라서 시작점과 끝점이 주어진다면 주어진 그래프에서 최단 경로를 알아낼 수 있다.

// BFS
public class No09BFS {

	Node root;

	public int BFS(Node root) {
		Queue<Node> q = new LinkedList<>();
		q.offer(root);

		int L = 0;
		while (!q.isEmpty()) {
			int len = q.size();
			for (int i = 0; i < len; i++) {
				Node cur = q.poll();
				if (cur.lt == null && cur.rt == null) return L;
				if (cur.lt != null) 	q.offer(cur.lt);
				if (cur.rt != null) q.offer(cur.rt);
				
			}
			L++;
		}

		return 0;
	}

	public static void main(String[] args) {
		No09BFS tree = new No09BFS();
		tree.root = new Node(1);
		tree.root.lt = new Node(2);
		tree.root.rt = new Node(3);
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);
		tree.root.rt.lt = new Node(6);
		tree.root.lt.lt.rt = new Node(7);
		tree.root.lt.rt.lt = new Node(8);
		
		System.out.println(tree.BFS(tree.root));

	}

}

// 노드 클래스
public class Node {
	int data;
	Node lt, rt;

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

출처 : 나무위키 - 너비 우선 탐색