[그래프 순회] BFS(너비 우선 탐색, Breadth-First Search)

BFS 알고리즘이란?

BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. 

주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있다.

 

BFS 알고리즘 작동 과정

1. 정점 i를 방문한다.
2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 큐에 저장한다.
3. 큐에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.
4. 큐가 공백이 되면 연산을 종료한다

 

배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다
- visited[i] = True : 방문하였음

- visited[i] = False: 방문하지 않음

 

그림 1 과 같은 그래프 예시를 통해 BFS 동작 과정을 알아보자. 노드 1을 시작 노드로 설정한다. 일반적으로 인접한 노드가 2개 이상인 경우에는 해당 노드들 중 번호가 낮은 노드부터 처리한다.

그림 1. BFS 동작 설명을 위한 그래프 예시

편의상 현재 큐에서 꺼내 처리 중인 노드는 파란색으로, 방문 처리한 노드는 회색으로 표시한다

 

(1) 시작 노드인 노드 1을 큐에 삽입하고 방문 처리 한다.

(2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 방문 처리한다.

(3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 방문 처리한다.

(4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 방문 처리한다.

(5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 방문 처리한다.

(6) 그래프 내 노드에서 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼낸다.

결과적으로 노드의 탐색 순서, 즉 큐에 삽입한 순서는 다음과 같다
1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7

 

 

 

수도코드

 

 

코드 구현

 

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// BFS 메서드 정의
void bfs(vector<vector<int>>& graph, int node, vector<bool>& visited) {
    // 큐 구현을 위한 queue 라이브러리 활용
    queue<int> q;
    // 시작 노드를 큐에 삽입하고 방문 처리
    q.push(node);
    visited[node] = true;

    // 큐가 완전히 빌 때까지 반복
    while (!q.empty()) {
        // 큐에서 노드 하나 꺼내기
        int v = q.front();
        q.pop();
        // 탐색 순서 출력
        cout << v << " ";

        // 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for (int i : graph[v]) {
            if (!visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    // 그래프 초기화
    vector<vector<int>> graph = {
        {},         // 0번 노드
        {2, 3},     // 1번 노드
        {1, 8},     // 2번 노드
        {1, 4, 5},  // 3번 노드
        {3, 5},     // 4번 노드
        {3, 4},     // 5번 노드
        {7, 8},     // 6번 노드
        {6, 8},     // 7번 노드
        {2, 6, 7}   // 8번 노드
    };

    // 방문 여부를 나타내는 배열 초기화
    vector<bool> visited(9, false);

    // 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
    bfs(graph, 1, visited);

    return 0;
}

 

Python

# deque 라이브러리 불러오기
from collections import deque

# BFS 메서드 정의
def bfs (graph, node, visited):
    # 큐 구현을 위한 deque 라이브러리 활용
    queue = deque([node])
    # 현재 노드를 방문 처리
    visited[node] = True
    
    # 큐가 완전히 빌 때까지 반복
    while queue:
        # 큐에 삽입된 순서대로 노드 하나 꺼내기
        v = queue.popleft()
        # 탐색 순서 출력
        print(v, end = ' ')
        # 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
        for i in graph[v]:
            if not (visited[i]):
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

# 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
bfs(graph, 1, visited)

 

실행 결과

1 2 3 8 4 5 6 7

 

 

 

Reference

https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습