너비 우선 탐색(BFS)

BFS

 

DFS는 연결된 노드 하나를 먼저 방문하는 것에 비해 BFS의 경우 연결된 노드 전체를 먼저 방문하는 것이 우선이 된다.

 

동작을 간단하게 보면 다음과 같다.

( 그래프는 DFS때와 동일한 무방향 그래프를 사용한다.)

 

예시 그래프의 BFS

2번 노드 부터 시작하면 먼저 큐에 2를 푸쉬해 둔다.

 

  1. poll하여 큐 최하단 노드를 꺼내어 방문 표시를 하고 출력한다.

  2. 해당 노드의 인접 노드중 미방문 노드를 전부 push한다.

  2. 큐가 빌때까지 1, 2번을 계속한다.

 

예시 그래프의 노드를 위 순서대로 진행하면 2 1 3 4 0가 된다.

 

코드

 

저번 dfs코드를 재귀호출이 아닌 스택을 직접적으로 사용할 경우 중복 제거를 했어야 함에 반해,

 

bfs의 특성상 중복 제거를 하지 않아도 결과는 동일하다.

import java.util.*;

public class graph {
	private int szVertex;
	private ArrayList<Integer> adjList[];
	private boolean visited[];
	private Queue<Integer> queue;				// for BFS
	
	public graph(int v) {
		szVertex = v;
		visited = new boolean[szVertex];		// default false
		adjList = new ArrayList[szVertex];
		for (int i = 0; i < szVertex; i++) {
			adjList[i] = new ArrayList();
		}
		queue = new LinkedList<Integer>();
	}
	
	public void addEdge(int from, int to) {
		// 무방향 그래프이므로 반대의 경우도 추가
		adjList[from].add(to);
		adjList[to].add(from);
	}
	
	// 재귀 호출로 구현할 수 있지만 queue을 이용하여 구현하였다
	public void BFS(int start) {
		queue.add(start);
		
		// queue가 비어질때까지 게속
		while (queue.peek() != null) {
			// queue에서 가장 오래전 삽입된 데이터를 꺼내어 방문 행렬에 표시하고 출력
			int current = queue.poll();
			
			// 미방문 정점의 경우
			if (!visited[current]) {
				visited[current] = true;
				System.out.print(current + " ");
				
				// 인접 리스트에서 미방문 정점의 경우 queue에 추가
				for (int i : adjList[current])
					if (!visited[i])
						queue.add(i);
			}
		}
		System.out.println();
	}
	
	// 첫노드가 주어지지 않을 경우 0번 부터
	public void BFS() {
		BFS(0);
	}
}

public class bfs {

	public static void main(String[] args) {
		graph g = new graph(5);
		
		g.addEdge(0, 1);
		g.addEdge(0, 4);
		g.addEdge(1, 2);
		g.addEdge(1, 3);
		g.addEdge(2, 3);
		g.addEdge(2, 4);
		
		g.BFS(2);
	}
}