[알고리즘] 너비 우선 탐색(BFS) 구현(C++, Python)

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

시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 알고리즘이다. 여기서 말하는 거리는 시작 노드와 목표 노드까지의 차수이다. 이러한 특성 때문에 너비 우선 탐색을 할 때는 큐를 활용한다.

2. 💡 BFS 알고리즘

• 일단 시작 노드를 정하고 큐에 시작 노드를 푸시한다. 시작 노드를 큐에 푸시하면서 방문 처리를 한다. 큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태라고 생각하면 된다. 이후 다음 과정을 반복한다.

1. 큐가 비었는지 확인한다. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미이다(탐색 종료).
2. 큐에서 노드를 팝한다.
3. 팝한 노드와 인접한 모든 노드를 확인하고 그중 아직 방문하지 않은 노드를 큐에 푸시하며 방문 처리한다.

3. ⚠️ 고려 사항

• 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 한다.
• 이미 방문한 노드인지 확인할 수 있어야 한다.

4. 🛠️ 큐를 활용한 BFS

• 방문한 노드는 하늘색이다. 그래프는 깊이 우선 탐색에서 다룬 그래프와 같다.
• 1단계: 시작 노드 1을 큐에 푸시하고 방문 처리한다.
• 2단계: 1을 팝한 후 인접한 4와 5를 본다. 아직 방문하지 않았으므로 방문 처리하고 4, 5 순서로 큐에 푸시한다.
• 3단계: 4를 팝한 후 인접한 2와 3을 본다. 아직 방문하지 않았으므로 방문 처리하고 2, 3 순서로 큐에 푸시한다.
• 4단계: 5를 팝한 후 인접한 1과 4를 본다. 이미 방문했으므로 아무것도 하지 않는다. 큐의 나머지 노드들도 자신과 인접한 노드들을 모두 방문했으므로 아무것도 하지 않고 팝한다. 큐가 비어 있으면 탐색을 마무리한 것이다.

5. 📝 코드 구현

    0
   / \
  1   2
 / \
3   4

5.1. C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfs(int startNode, const vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    // 시작 노드를 큐에 추가하고 방문 처리
    q.push(startNode);
    visited[startNode] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        // 인접한 노드 탐색
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true; // 방문 처리
            }
        }
    }
}

int main() {
    // 그래프 정의 (예: 0-1-2-3-4)
    vector<vector<int>> graph = {
        {1, 2},    // 0
        {0, 3, 4}, // 1
        {0},       // 2
        {1},       // 3
        {1}        // 4
    };

    bfs(0, graph); // 시작 노드: 0
    return 0;
}

5.2. Python

from collections import deque

def bfs(start_node, graph):
    visited = [False] * len(graph)
    q = deque()

    # 시작 노드를 큐에 추가하고 방문 처리
    q.append(start_node)
    visited[start_node] = True

    while q:
        node = q.popleft()
        print(node, end=" ")

        # 인접한 노드 탐색
        for neighbor in graph[node]:
            if not visited[neighbor]:
                q.append(neighbor)
                visited[neighbor] = True  # 방문 처리

if __name__ == "__main__":
    # 그래프 정의 (예: 0-1-2-3-4)
    graph = {
        0: [1, 2],
        1: [0, 3, 4],
        2: [0],
        3: [1],
        4: [1]
    }

    bfs(0, graph)  # 시작 노드: 0

Algorithm Theory 카테고리 내 다른 글 보러가기