[C] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리

개념

너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로,

동작 과정이 직관적이여서 이해하기 쉽다

 

[그림 1] 그래프의 너비 우선 탐색 (출처 : 알고리즘 문제 해결 전략)

(a)의 그래프에서, a를 탐색의 시작점이라고 하자

H0의 a를 방문하고, H1의 b d e h, 그리고 H2, H3에 속한 정점들을 순서대로 방문해 나간다

이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 먼저 꺼내는 것이다

시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문이다

이 조건을 큐를 사용하여 만족시킬 수 있게 된다

snupi.tistory.com/20

[C code] 원형 큐 (Circular Queue)

 

---

코드

인접 행렬을 이용하였다

#include<stdio.h>

#define MAX 1001
int adj[MAX][MAX]; // 인접행렬 만들때 사용
int discovered[MAX]; // BFS_발견했는지 check

typedef struct Queue
{
int front, rear;
int data[MAX];
}Queue;

void BFS(int start, int N) {
    int here, there;

    Queue q;
    q.front = -1;
    q.rear = -1;

    discovered[start] = 1; // 발견 정점 최적화
    q.data[++q.rear] = start; // push

    //queue 꺼내기
    while(q.front < q.rear) {
        here = q.data[++q.front]; // pop
        printf("%d ", here);

        //인접행렬 구하기
        for(int i=1; i<=N; i++) {
            if(adj[here][i]) {
                there = i;

                if(!discovered[there]) {
                    discovered[there] = 1;
                    q.data[++q.rear] = there; // push
                }
            }
        }
    }
}

int main() {
    int N,M,v; // 정점개수, 간선개수, 시작정점
    int x,y; // 좌표

    scanf("%d %d %d", &N, &M, &v);
    for(int i=1; i<=M; i++) { //M(간선개수) 만큼
        scanf("%d %d", &x,&y);
        adj[x][y]=1;
        adj[y][x]=1; //인접행렬 만들기
    }

    //BFS 호출
    BFS(v, N);

    return 0;
}

 

DFS와 달리 발견과 방문이 같지 않아 모든 정점은 다음과 같은 3개의 상태를 순서대로 거친다

(discovered[] 은 visited[] 과 다르다)

 

1. 아직 발견 X
2. 발견 O, 방문 X (큐에 저장)
3. 방문까지 O

그리고 BFS에서 새 정점을 발견하는 데 사용했던 간선들만을 모은 트리를

너비 우선 탐색 스패닝 트리(BFS Spanning Tree)라고 한다

 

---

시간 복잡도

이 역시 DFS와 마찬가지다

 

인접 리스트를 이용했을 때,

모든 정점을 한 번씩, 간선을 1번 (무향 그래프일 경우 2번) 확인하므로

O(|V| + |E|) 가 된다

(|V|는 정점 수, |E|는 간선 수)

 

인접 행렬을 사용한다면 dfs() 내부에서 다른 모든 정점들을 순회하며 간선을 확인하므로

O(|V|^2) 가 된다

 

---

최단 경로 알고리즘

BFS는 주로 딱 하나의 용도로 사용되는데, 바로 그래프의 최단 경로 문제이다

가중치가 없는 그래프를 다루도록 해보자

 

BFS를 간단히 변경해 모든 정점에 대해 distance[]를 계산할 수 있다

예를 들어 간선 (u, v)를 통해 distance[v] = distance[u] + 1 임을 알 수 있다

 

코드 구현도 간단하다

BFS 스패닝 트리를 일반적인 트리, 그래프 형태로 저장하는 대신

각 정점의 부모 번호만으로 표현하여 쉽게 계산할 수 있다

 

#include<stdio.h>

#define MAX 1001
int adj[MAX][MAX]; // 인접행렬 만들때 사용
int distance[MAX];
int parent[MAX];

typedef struct Queue
{
int front, rear;
int data[MAX];
}Queue;

void init(int N) {
    for(int i = 1; i <= N; i++)
    {
        distance[i] = -1;
        parent[i] = -1;
    }
}

void BFS2(int start, int N) {
    int here, there;

    Queue q;
    q.front = -1;
    q.rear = -1;

    distance[start] = 0;
    parent[start] = start;
    q.data[++q.rear] = start; // push
    
    //queue 꺼내기
    while(q.front < q.rear) {
        here = q.data[++q.front]; // pop

        //인접행렬 구하기 (DFS for문과 if문 똑같다)
        for(int i=1; i<=N; i++) {
            if(adj[here][i]) {
                there = i;

                if(!distance[there]) {
                    distance[there] = distance[here] + 1;
                    parent[there] = here;
                    q.data[++q.rear] = there; // push
                }
            }
        }
    }
}

void ShortestPath(int v, int N) {
    int path[N];
    
    while(parent[v] != v) {
        v = parent[v];
        // ---path에 v 추가---
    }
    // ---path 뒤집기---
}

int main() {
    int N,M,v; // 정점개수, 간선개수, 시작정점
    int x,y; // 좌표

    scanf("%d %d %d", &N, &M, &v);
    for(int i=1; i<=M; i++) { //M(간선개수) 만큼
        scanf("%d %d", &x,&y);
        adj[x][y]=1;
        adj[y][x]=1; //인접행렬 만들기
    }

    //init 호출
    init(N);

    //BFS 호출
    BFS2(v, N);
    ShortestPath(v, N);

    return 0;
}

 

---

더 나아가기 키워드

• 양방향 탐색
• 점점 깊어지는 탐색(IDS; Iteratively Deepening Search)
• BFS의 최단 경로 문제 알고리즘
  - 다익스트라의 최단 경로 알고리즘
  - 벨만-포드의 최단 경로 알고리즘
  - 플로이드의 모든 쌍 최단 거리 알고리즘
• BFS의 최소 스패닝 트리
  - 프림의 최소 스패닝 트리 알고리즘
  - 크루스칼의 최소 스패닝 트리 알고리즘