[알고리즘] 탐색 알고리즘 기본적인 이해와 구현 - 7. 너비 우선 탐색

1. 선형 탐색 (Linear Search)
2. 이진 탐색 (Binary Search)
3. 점프 탐색 (Jump Search)
4. 보간 탐색 (Interpolation Search)
5. 지수 탐색 (Exponential Search)
6. 깊이 우선 탐색 (Depth-First Search, DFS)
7. 너비 우선 탐색 (Breadth-First Search, BFS)

 

 

너비 우선 탐색

너비 우선 탐색은 트리나 그래프에서 시작 노드에서 가까운 노드부터 순차적으로 탐색하는 방식입니다. 이 방법은 한 노드에서 출발하여 인접한 모든 노드를 탐색한 후, 점차 멀리 있는 노드를 탐색하는 방식으로 진행됩니다. BFS는 주로 큐를 사용해 구현하며, 최단 경로 찾기 문제에 유용합니다.

 

1. 특징

• 큐 기반: BFS는 큐 자료구조를 이용하여 구현되며, 큐에 의해 노드들이 탐색 순서대로 저장됩니다.
• 계층적 탐색: 특정 노드로부터 각 거리를 기준으로 순차적으로 탐색하기 때문에, 최단 거리 탐색에 유리합니다.
• 모든 경로를 탐색: 깊이 우선 탐색과 달리 너비 우선 탐색은 특정 노드에 가까운 모든 경로를 동시에 탐색합니다.

 

 

2. 복잡도

• 시간 복잡도: O(V+E)O(V + E)O(V+E), 여기서 VVV는 노드(정점)의 개수, EEE는 간선의 개수입니다.
• 공간 복잡도: 큐에 의해 추가적인 공간 O(V)O(V)O(V)가 사용됩니다.

 

3. 예제

import java.util.*;

public class BFSExample {
    public static void bfs(int startNode, List<List<Integer>> graph) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();

        visited[startNode] = true;
        queue.add(startNode);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // 현재 노드와 연결된 모든 노드를 방문
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; // 노드 개수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 연결 (양방향)
        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(1).add(4);

        System.out.println("BFS 시작:");
        bfs(0, graph);
    }
}

• 이 코드에서는 특정 시작 노드에서 BFS 탐색이 시작되어 인접한 노드를 순차적으로 큐에 넣고, 인접한 노드를 너비 우선으로 탐색해 나갑니다.

 

4. 주 사용처

• 최단 경로 탐색: BFS는 가중치가 없는 그래프에서 특정 노드로부터 모든 노드까지의 최단 경로를 찾는 데 자주 사용됩니다.
• 그래프의 연결 요소 탐색: BFS는 특정 노드와 연결된 모든 노드를 탐색하기 때문에 그래프의 연결 요소 탐색에 적합합니다.
• 네트워크 연결 및 검색 알고리즘: 소셜 네트워크에서 사용자와 친구들 간의 관계를 분석하거나, 웹 크롤링과 같은 알고리즘에서 깊이 있는 노드 검색을 제한하기 위해 유용하게 사용됩니다.

 

감사합니다.