9-5. [C/C++] 그래프의 탐색 - 너비 우선 탐색, BFS

그래프 탐색

그래프 탐색은 하나의 정점에서 시작해 모든 정점들은 한 번씩 방문하는 그래프의 가장 기본적인 연산이다.

그래프의 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.

---

너비 우선 탐색

너비 우선 탐색(breadth first search, BFS)은 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 그래프 순회 방법이다.

 

BFS는 임의의 노드에서 가장 가까운 노드를 먼저 탐색한다.

가까이 있다면 당연하게 먼저에 만나게 될 것이다.

"먼저 만난 노드를 먼저 탐색한다." 큐 자료구조의 특징과 비슷하다는 것을 알 수 있다.

그래서 BFS에서는 큐를 사용한다.

 

BFS의 동작 과정을 보자.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

아래 그림을 보며 BFS의 과정을 살펴보자.

BFS 시간 복잡도

BFS는 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프를 DFS하는 시간은

인접 리스트를 이용한 그래프의 경우 O(n + e) 이고, 인접 행렬을 이용한 그래프의 경우 O(n²) 이다.

시간 복잡도에서도 알 수 있듯이, 희소 그래프인 경우 인접 리스트를 사용하는 것이 더 좋다.

---

위에서 BFS는 큐를 사용한다고 했다. DFS에서는 스택을 구현하지 않고 재귀 함수를 사용했다.

하지만 BFS에서는 큐를 구현해서 사용한다. 전에 구현했던 큐를 그대로 사용하자.

인접 행렬을  이용한 그래프의 BFS

전에 구현했던 AdjMatGraph 클래스를 상속해서 BFS를 위한 MatGraphForBFS 클래스를 구현했다.

// MatGraphForBFS.h
#include "AdjMatGraph.h"
#include "circularQueue.h"

class MatGraphForBFS : public AdjMatGraph {
    bool visited[MAX_SIZE];

public:
    MatGraphForBFS(int size) : AdjMatGraph(size) {}
    void reset() {
        for (int i = 0; i < size; i++) {
            visited[i] = false;
        }
    }

    bool isLinked(int u, int v) { return getEdge(u, v) == 1; }

    void bfs(int v) {
        visited[v] = true;
        cout << "[" << v << "] ";

        CircularQueue queue;
        queue.enqueue(v);

        while (!queue.isEmpty()) {
            int cur = queue.dequeue();

            for (int u = 0; u < size; u++) {
                if (isLinked(cur, u) && visited[u] == false) {
                    visited[u] = true;
                    cout << "[" << u << "] ";
                    queue.enqueue(u);
                }
            }
        }
    }
};

// MatGraphForBFS.cpp
#include "MatGraphForBFS.h"

int main() {
    MatGraphForBFS graph(4);

    graph.insertEdge(0, 1);
    graph.insertEdge(0, 3);
    graph.insertEdge(1, 2);
    graph.insertEdge(1, 3);
    graph.insertEdge(2, 3);

    graph.display();
    graph.bfs(0); cout << endl;
}

/*
실행 결과:
Graph by Adjacency Matrix
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
[0] [1] [3] [2]
*/

인접 리스트를 이용한 그래프의 BFS

전에 구현했던 AdjListGraph 클래스를 상속해서 DFS를 위한 ListGraphForDFS 클래스를 구현했다.

// ListGraphForBFS.h
#include "AdjListGraph.h"
#include "circularQueue.h"

class ListGraphForBFS : public AdjListGraph {
    bool visited[MAX_SIZE];

public:
    ListGraphForBFS(int size) : AdjListGraph(size) {}

    void reset() {
        for (int i = 0 ;i < size; i++) {
            visited[i] = false;
        }
    }

    bool isLinked(int u, int v) {
        for (Node *cur = graph[u]; cur != NULL; cur = cur->getLink()) {
            if (cur->getVertex() == v) return true;
        }
        return false;
    }

    void bfs(int v) {
        visited[v] = true;
        cout << "[" << v << "] ";

        CircularQueue queue;
        queue.enqueue(v);

        while (!queue.isEmpty()) {
            int cur = queue.dequeue();

            for (Node *u = graph[cur]; u != NULL; u = u->getLink()) {
                int curV = u->getVertex();
                if (!visited[curV]) {
                    visited[curV] = true;
                    cout << "[" << curV << "] ";
                    queue.enqueue(curV);
                }
            }
        }
    }
};

// ListGraphForBFS.cpp
#include "ListGraphForBFS.h"

int main() {
    ListGraphForBFS graph(4);

    graph.insertEdge(0, 1);
    graph.insertEdge(0, 3);
    graph.insertEdge(1, 2);
    graph.insertEdge(1, 3);
    graph.insertEdge(2, 3);

    graph.display();
    graph.bfs(0); cout << endl;
}

/*
실행 결과:
Graph by Adjacency List
3 1
3 2 0
3 1
2 1 0
[0] [3] [1] [2]
*/

실행 결과가 인접 행렬을 이용했을 때와 다르다.

인접 리스트의 노드 순서때문에 결과는 다를 수 있다.

BFS는 그래프를 순회하는 방법일 뿐이라서 노드가 들어가 있는 순서에 따라 결과는 다를 수 있다.

하지만 과정은 동일하다.

 

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.