[알고리즘] BFS(너비 우선 탐색)

BFS와 DFS

대표적인 그래프 탐색 알고리즘

• 너비 우선 탐색(Breadth First Search): 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
• 깊이 우선 탐색(Depth First Search): 정점의 자식들을 먼저 탐색하는 방식

 

BFS/DFS 방식 이해를 위한 예제

1. BFS 방식: A - B - C - D - G - H - I - E - F - J 

• 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 순회함

2. DFS 방식: A - B - D - E - F - C - G - H - I - J 

• 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순화함

 

 

Java로 그래프를 표현

• Java에서는 HashMap<String, List<String>> 자료구조를 사용해서 표현할 수 있음

 

그래프 예와 표현

 

import java.util.*;

public class GraphExample {
    public static void main(String[] args) {
        // 그래프 선언
        Map<Character, List<Character>> graph = new HashMap<>();
        graph.put('A', Arrays.asList('B', 'C'));
        graph.put('B', Arrays.asList('A', 'D'));
        graph.put('C', Arrays.asList('A', 'G', 'H', 'I'));
        graph.put('D', Arrays.asList('B', 'E', 'F'));
        graph.put('E', Arrays.asList('D'));
        graph.put('F', Arrays.asList('D'));
        graph.put('G', Arrays.asList('C'));
        graph.put('H', Arrays.asList('C'));
        graph.put('I', Arrays.asList('C', 'J'));
        graph.put('J', Arrays.asList('I'));

        // 그래프 출력
        for (String node : graph.keySet()) {
            System.out.println(node + " -> " + graph.get(node));
        }
    }
}

 

BFS 알고리즘 구현

자료구조 Queue를 활용함

• needVisit와 visited 두 개의 큐를 생성

🤔 Queue를 사용하는 이유?
너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식!
따라서 인접한 정점들에 대해 탐색을 한 후 차례로 다시 너비 우선 탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용하여 인접한 정점들을 저장해놔야 함

 

public static void bfs(Map<Character, List<Character>> graph, char start) {
    Queue<Character> queue = new ArrayDeque<>();
    Set<Character> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);

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

        for (char neighbor : graph.getOrDefault(current, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

탐색 결과

[A, B, C, D, G, H, I, E, F, J]

 

 

인접 리스트 vs 인접 행렬: BFS 구현으로 알아보기

1) 인접 리스트 기반 BFS

인접 리스트란?

• 각 정점마다 연결된 노드의 리스트를 저장
• 공간 복잡도: O(V + E)
• 간선이 많지 않은 희소 그래프(Sparse Graph)에 적합

 

구조 설명

• adjList[i]는 정점 i에 연결된 노드들을 연결 리스트로 표현
• Node 클래스는 vertex(정점 번호)와 link(다음 노드)를 포함
• 연결된 모든 정점을 순회하며 큐에 추가

 

+ 인접 리스트로 BFS 구현하는 두 가지 방식

1. Node 클래스를 이용한 연결 리스트 방식

구조: 각 정점마다 연결된 노드를 노드 객체(Node)로 연결해 관리

private static class Node {
    int vertex;     // 연결된 정점
    Node link;      // 다음 노드
    
    public Node(int vertex, Node link) {
        this.vertex = vertex;
        this.link = link;
    }

    // alt + shift + s
    @Override
    public String toString() {
        return "Node [vertex=" + vertex + ", link=" + link + "]";
    }
}

구현 코드 요약

adjList[from] = new Node(to, adjList[from]);  // 유향
adjList[to] = new Node(from, adjList[to]);    // 무향

BFS 탐색

for (Node temp = adjList[current]; temp != null; temp = temp.link) {
    if (!visited[temp.vertex]) {
        queue.offer(temp.vertex);
        visited[temp.vertex] = true;
    }
}

장점	연결을 직접 관리하므로 메모리 절약 가능 데이터 구조에 대한 직접적인 제어가 가능
단점	코드 구조가 복잡해짐 (Node 클래스 관리 필요) 디버깅이나 유지보수가 어려울 수 있음

 

2. List<Integer>[] 배열을 사용하는 방식

구조: 각 정점에 대해 연결된 정점들을 ArrayList로 관리

List<Integer>[] adjList = new ArrayList[V];

구현 코드 요약

adjList[from].add(to);   // 유향
adjList[to].add(from);   // 무향

BFS 탐색

for (int vertex : adjList[current]) {
    if (!visited[vertex]) {
        queue.offer(vertex);
        visited[vertex] = true;
    }
}

장점	코드가 간단하고 직관적 자바의 컬렉션 프레임워크를 활용 → 사용성↑, 가독성↑ 학습용, 구현 연습에 적합
단점	Node 객체 방식에 비해 연결 관계를 상세하게 표현하기는 어려움

 

코드 예시(공통 BFS 로직)

private static void bfs(int start) { // start: 시작 정점
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[V]; // 중복 방문 피하기 위해

    queue.offer(start); // 큐에 넣어 방문 예약
    visited[start] = true; // 큐에 넣을 땐 반드시 방문 체크

    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print((char)(current + 65) + " "); // 정점 방문했을 때 할 일 수행

        // 인접 정점 순회
        for (...) {
            if (!visited[neighbor]) { // 이동할 정점을 방문 했는지 확인
                queue.offer(neighbor); // 큐에 넣어 방문 예약
                visited[neighbor] = true; // 큐에 넣을 땐 반드시 방문 체크
            }
        }
    }
}

 

2) 인접 행렬 기반 BFS

인접 행렬이란?

• 2차원 배열을 이용하여 adjMatrix[i][j] = 1이면 i와 j가 연결되었음을 나타냄
• 공간 복잡도: O(V²)
• 노드 간 연결이 많은 밀집 그래프(Dense Graph)에 적합

 

구조 설명

• adjMatrix[i][j]가 1이면 두 정점 간 간선이 존재함
• 각 정점의 모든 열을 순회하면서 연결된 정점을 탐색

 

코드 예시

private static void bfs(int start) { // start: 시작 정점
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[V];

    queue.offer(start); // 큐에 넣어 방문 예약
    visited[start] = true; // 큐에 넣을 땐 반드시 방문 체크

    while (!queue.isEmpty()) {
        int current = queue.poll();
        System.out.print((char) (current + 65) + " "); // 정점을 방문했을 때 할 일 수행

        for (int i = 0; i < V; i++) {
        	// 인접하고 방문하지 않은 정점이면
            if (adjMatrix[current][i] != 0 && !visited[i]) {
                queue.offer(i); // 큐에 넣어 방문 예약
                visited[i] = true; // 큐에 넣을 땐 반드시 방문 체크
            }
        }
    }
}

 

인접 리스트 vs 인접 행렬 비교 요약

항목	인접 리스트	인접 행렬
공간 복잡도	O(V + E)	O(V²)
간선 탐색 속도	연결 리스트 순회 (보통 빠름)	배열 순회 (V개 비교 필요)
적합한 경우	간선 수가 적은 희소 그래프	간선 수가 많은 밀집 그래프
구현 난이도	비교적 복잡 (Node 클래스 필요)	단순한 2차원 배열 사용
BFS 시간 복잡도	O(V + E)	O(V²) (행 전체를 탐색)

 

시간 복잡도

• 일반적인 BFS 시간 복잡도: O(V + E)
  • 노드 수: V / 간선 수: E
  • 즉 values의 총 개수

• 각 노드는 최대 한 번만 큐에서 꺼내져 방문됨 → O(V)
• 각 간선은 양쪽 끝 노드에서 한 번씩 큐에 추가될 수 있음 → O(E)