[자료구조] BFS

그래프를 탐색하는 방법에는 DFS, BFS 알고리즘이 있다. 이번엔 BFS에 대해 정리해 보겠다.

2. BFS

BFS는 현재 노드에서 이동 가능한 다음 레벨의 노드를 모두 확인한 후, 다음 레벨의 노드들을 모두 큐(Queue)에 담는다  이후 큐에 담긴 노드 위치들을 하나씩 꺼내며 다음 방문할 노드들을 탐색한다. . DFS가 갈 수 있는데 까지 깊게 갔다면, BFS는 일단 주변에 연결된 노드들을 먼저 방문하여 넓게 탐색하는 알고리즘이다.

• 필요한 것
  • 큐: 방문 차례의 기록을 목적으로 함
  • 배열: 방문 정보의 기록을 목적으로 함

 

<BFS의 특징>

• DFS와 달리 BFS는 재귀적으로 동작하지 않는다.
• BFS를 구현할 때, 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않으면 무한루프에 빠질 수 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(queue)를 사용한다. 
  • 선입선출(First In First Out) 원칙으로 탐색
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
• BFS의 시간 복잡도
  • 인접 행렬 그래프: O(V+E)
  • 인접 리스트 그래프: O(V*V)
• DFS와 마찬가지로 간선 수가 정점 수보다 적은 희소 그래프 (Sparse Graph)의 경우 인접 리스트가 인접 행렬보다 유리하다.
• 장점
  • 출발노드에서 목표노드까지 최단 길이 경로를 보장한다. (가중치가 동일할 경우)
• 단점
  • 최악의 경우 모든 노드들을 탐색하게 되므로 모든 노드에 대한 저장공간을 크게 잡아야 함
  • 목표노드가 깊은 단계에 있는 경우 오랜 시간이 소요됨

 

<BFS의 탐색 과정>

최초에 방문할 노드를 큐에 삽입한다. 

1에 인접한 노드들을 큐에 넣어준다. 이 때 노드들의 큐에 삽입과 동시에 방문했다고 체크해야 한다! 

큐에서 다음 노드를 pop한다. 2가 현재 정점이 되고 2의 인접해있는 노드 3, 4를 큐에 삽입한다. 

여기서 5는 이미 방문한 노드이므로 큐에 삽입하지 않는다. 

큐에서 다음 정점 5를 팝한다. 그러나 5와 인접한 노드들은 전부 방문했기 때문에 그대로 끝난다.

정점 3도 인접한 노드들도 이미 전부 방문했기 때문에 마찬가지로 종료한다.

 

정점 4의 인접 노드 중에 방문하지 않은 정점 6을 큐에 삽입한다. 큐가 비었으므로 프로그램을 종료한다. 왼쪽 이미지엔 큐가 비어있는데 왜 종료 안되냐고 묻는다면 큐가 비었는지 검사하는 조건문 다음에 큐에서 pop했기 때문이다.

 

 

<인접 행렬로 구현한 BFS>

package graph;

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

public class BFS {
	
	static int V;
	static int E;
	static int[][] ad;
	static boolean[] checked;

	public static void bfs(int x) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(x);
		checked[x] = true;
		
		while(!q.isEmpty()) {
			int u = q.poll();				
			System.out.println(u);
			
			for(int i = 1; i <= V; i++) {
				if(ad[u][i] == 1 && !checked[i]) {
					q.offer(i);
					checked[i] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();
		ad = new int[V+1][V+1];
		checked = new boolean[V+1];
		
		for(int i = 0; i < E; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			
			ad[u][v] = ad[v][u] = 1;
		}
		
		bfs(1);
	}

}

결과