BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도

 

BFS

 

BFS(Breadth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 가까운 노드부터 탐색을 진행합니다. 경로를 찾거나 최단 거리를 계산하는 데 유용하며, 다양한 문제 해결에 활용됩니다.

---

 

1. BFS의 개념

BFS는 큐(Queue) 자료구조를 기반으로 작동하며, 그래프의 각 레벨을 순차적으로 탐색합니다. 그래프의 각 정점을 방문하면서 모든 인접한 정점을 차례대로 탐색하므로, 깊이보다는 너비를 우선시합니다.

---

 

2. BFS의 동작 원리

1. 시작 정점을 큐에 삽입하고 방문 처리합니다.
2. 큐에서 정점을 하나씩 꺼내어 해당 정점의 모든 인접 정점을 탐색합니다.
3. 인접 정점 중 방문하지 않은 정점을 큐에 삽입하고 방문 처리합니다.
4. 큐가 빌 때까지 위 과정을 반복합니다.

동작 구조도

반응형

다음은 BFS의 동작 과정을 시각적으로 표현한 구조도입니다.

BFS로 탐색하려는 그래프 연결관계

시작 정점: A

1단계: 큐=[A]
    A 탐색 → 인접 정점 B, C, D 큐에 추가
    방문 순서: A

2단계: 큐=[B, C, D]
    B 탐색 → 인접 정점 E 추가 (이때 C도 B와 인접해있지만, C는 이미 큐에 들어가있으므로 생략)
    방문 순서: A → B

3단계: 큐=[C, D, E]
    C 탐색 → 인접 정점 F 추가
    방문 순서: A → B → C

4단계: 큐=[D, E, F]
    ...

이와 같이 BFS는 가까운 정점부터 차례대로 탐색을 진행합니다.

---

 

3. BFS의 시간 복잡도

• 시간 복잡도: O(V + E)
  • V: 정점(Vertex)의 수
  • E: 간선(Edge)의 수
  • 각 정점을 한 번씩 방문하고, 모든 간선을 확인하기 때문입니다.
• 공간 복잡도: O(V)
  • 큐에 저장되는 정점 개수와 방문 여부를 기록하는 배열이 필요합니다.

---

 

4. BFS 구현 예시 코드

C 언어 구현

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

int graph[MAX][MAX];
bool visited[MAX];
int queue[MAX];
int front = 0, rear = 0;

void enqueue(int v) {
    queue[rear++] = v;
}

int dequeue() {
    return queue[front++];
}

bool isEmpty() {
    return front == rear;
}

void bfs(int start, int n) {
    enqueue(start);
    visited[start] = true;

    while (!isEmpty()) {
        int current = dequeue();
        printf("%d ", current);

        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    int n = 6;

    graph[0][1] = graph[0][2] = 1;
    graph[1][3] = graph[1][4] = 1;
    graph[2][5] = 1;

    bfs(0, n);

    return 0;
}

 

Java 구현

import java.util.*;

public class BFS {
    public static void main(String[] args) {
        int n = 6;
        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);
        graph.get(2).add(5);

        bfs(graph, 0);
    }

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

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

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

            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }
}

 

Python 구현

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        current = queue.pop(0)

        if current not in visited:
            print(current, end=' ')
            visited.add(current)
            queue.extend(graph[current])

# 그래프 예시
graph = {
    0: [1, 2],
    1: [3, 4],
    2: [5],
    3: [],
    4: [],
    5: []
}

bfs(graph, 0)

---

 

5. BFS의 장단점

장점

1. 최단 경로 보장: 무가중 그래프에서 시작 정점에서 목표 정점까지의 최단 경로를 보장합니다.
2. 모든 경로 탐색 가능: 그래프의 모든 정점을 방문할 수 있습니다.

단점

1. 공간 요구량: 큐와 방문 상태를 저장하기 위해 더 많은 메모리가 필요합니다.
2. 가중 그래프의 최단 경로 계산 불가: 가중치가 있는 그래프에서는 다익스트라 알고리즘 등이 필요합니다.

---

BFS는 그래프 탐색의 기초를 이루는 중요한 알고리즘으로, 다양한 문제 해결에 널리 사용됩니다.

 

 

참고) DFS, BFS 비교

2024.12.19 - [알고리즘] - DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도)

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 비교(차이점, 장단점, 예시코드, 활용도)