BFS(Breadth-First Search, 너비 우선 탐색)

 

BFS는 그래프 탐색 알고리즘으로 시작 노드에서 가까운 노드부터 차례로 탐색하는 방식이다. BFS는 큐 자료 구조를 사용하여 탐색을 진행한다.

BFS의 동작 과정

1. 시작 노드를 큐에 삽입하고 방문 처리한다.
2. 큐에서 노드를 꺼내 해당 노드와 인접한 모든 방문하지 않은 노드를 큐에 삽입하고, 방문 처리한다.
3. 큐가 빌 때까지 2번 과정을 반복한다.

BFS의 시간 복잡도는 O(V + E)이다.
V: 정점의 개수
E: 간선의 개수

• 최단 경로 탐색: 가중치가 없는 그래프에서 최단 경로를 찾는데 유용하다.
• 그래프의 연결성을 확인할 때 쓸 수 있다.
  1. BFS를 수행하면서 방문한 노드를 기록한다.
  2. BFS 종료 후 방문하지 않은 노드가 있으면 그래프는 비연결 그래프이다.
  3. 모든 노드를 방문했다면 그래프는 연결된 그래프이다.

import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.Queue;  

public class BFS {  
    public static void bfs(int start, List<List<Integer>> graph){  
        boolean[] visited = new boolean[graph.size()]; // 방문여부 배열  
        Queue<Integer> queue = new LinkedList<>(); // 큐 생성  

        queue.add(start); // 시작 노드를 큐에 삽입  
        visited[start] = true; // 시작 노드 방문 처리  

        while(!queue.isEmpty()){  
            int node = queue.poll(); // 큐에서 노드 꺼내기  
            System.out.println("Visited node: " + node);  

            // 현재 노드와 인접한 노드 탐색  
            // graph는 리스트의 리스트(List<List<Integer>>)이다.  
            // graph.get(node)는 노드에 연결된 모든 노드(인접 노드)가 포함된 리스트를 반환한다.  
            // 연결그래프로 구현한 그래프로 너비 순서로 인접 노드에 차례대로 방문한다.  
            // bfs는 꼭 트리에서 쓰이는 게 아니라 그래프에서 범용적으로 쓰이는 탐색 알고리즘이다.  
            for(int neighbor : graph.get(node)){  
                if(!visited[neighbor]){  
                    queue.add(neighbor);  
                    visited[neighbor] = true;  
                }  
            }  
        }  
    }  

    public static void main(String[] args){  
        List<List<Integer>> graph = new ArrayList<>();  
        for(int i = 0; i < 5; i++){ // 정점 0 ~ 4            graph.add(new ArrayList<>());  
        }  

        // 간선 추가  
        graph.get(0).add(2);  
        graph.get(0).add(1);  
        graph.get(1).add(0);  
        graph.get(1).add(3);  
        graph.get(2).add(0);  
        graph.get(2).add(4);  
        graph.get(3).add(1);  
        graph.get(4).add(2);  

        bfs(0, graph); // 0번 노드에서 탐색 시작  
    }  
}  

//    0  
//    / \  
//    2   1  
//    \    \  
//    4     3