📚 BFS

BFS (Breadth-First-Search), 너비우선탐색은 앞서 소개한 DFS와 다르게 한 레벨 한 레벨씩 탐색해나가는 과정이다.
재귀로 할 수도 있지만, 큐를 이용해서 간단하게 구현할 수 있다.

💻 Implementation

재귀 버전

	public void bfs() {
		boolean[] visited = new boolean[nodes];
		LLQueue<Integer> q = new LLQueue<Integer>();
		for (int i=0;i<nodes;i++)
			visited[i] = false;

		for (int i=0;i<nodes;i++) {
			q.enqueue(i);
			doBfs(visited, q);
		}
	}

	public void doBfs(boolean[] visited, LLQueue<Integer> q) {
		int node;

		if (q.isEmpty()) return ;
		node = q.dequeue();
		if (visited[node] == true) return;
		visited[node] = true;
		System.out.println(node);
		for (int i=0;i<nodes;i++) 
			if (visited[i] == true && adj[node][i] == true)
				q.enqueue(i);
		doBfs(visited, q);
	}

이렇게 큐를 이용해서 넘겨주면 된다.

그래프가 이런 모양이라면 bfs 시 0-1-2-3-4-5 가 나와야 한다.

역시 잘 나온다.

Non-recursive version

	public void bfsQ() {
		boolean[] visited = new boolean[nodes];
		LLQueue<Integer> q = new LLQueue<Integer>();
		for (int i=0;i<nodes;i++)
			visited[i] = false;

		for (int i=0;i<nodes;i++) {
			q.enqueue(i);
			int node;

			while (!q.isEmpty()) {
				node = q.dequeue();
				if (visited[node]) continue;
				System.out.println(node);
				visited[node] = true;
				for (int j=0;j<nodes;j++)
					if (!visited[j] && adj[node][j])
						q.enqueue(j);
			}
		}

⌛️ Time Complexity

시간 복잡도는 dfs와 동일하게 ${O(|V|^2)}$ 또는 ${O(|V|+|E|)}$이다.

BFS -> 최단경로 찾기

트리로 치면 BFS를 통해 도출된 경로가 최단경로이다.