넓이 우선 탐색 (BFS : Breadth Frist Search) - JAVA

깊이 우선 탐색(DFS : Depth First Search)

---

너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다.

출처 : https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

FIFO(First In First Out) 방식으로 큐를 이용하여 구현하며 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다.

 

장단점

• 장점
  • 시작 노드부터 목표 노드 까지의 최단 경로를 보장
• 단점
  • 큐를 이용해 다음에 탐색 할 노드를 저장하기 때문에 노드의 수가 많을 수로 많은 저장 공간을 필요로함
  • 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기 때문에 비효율적

 

구현 방법

---

BFS를 사용하기 위해서는 먼저 그래프를 구현 해야합니다. 그래프를 구현하는 방법은 인접 행렬과 인접 리스트 2가지의 방법이 있습니다. 이에 대한 정보는 아래의 주소에서 확인 할 수 있습니다.

인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) - JAVA

 

BFS를 구현 하는 방법은 큐를 이용하여 구현할 수 있습니다.

 

구현

// 인접리스트 사용시
ArrayList<ArrayList<Integer>> graph;
boolean[] visited;

Queue<Integer> queue = new LinkedList<>();

// 1부터 N 까지의 노드 모두 탐색
for(int i = 1; i <= N; i++) {
    if(!visited[i]) {
    	// queue에 시작 노드 추가
        queue.add(i);
        // 방문 체크
        visited[i] = true;
        
        // queue가 비어있는 경우 탐색 완료
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            ArrayList<Integer> curList = graph.get(cur);
            
            for(int j = 0; j < curList.size(); j++) {
            	// 인접한 노드에서 방문하지 않은 노드 queue에 추가
                if(!visited[curList.get(j)]) {
                    visited[curList.get(j)] = true;
                    queue.add(curList.get(j));
                }
            }
        }
	}
}

그래프가 모두 연결되어 사이클(Cycle)을 형성하게 되면 이미 방문한 노드를 계속해서 방문하게 되어 무한 루프를 돌게되는 경우를 주의 해야합니다. 때문에 boolean 형태의 visited 배열을 두어 방문의 유무를 체크하며 방문하여 문제를 해결 하면 되겠습니다.