너비 우선 탐색(BFS, Breadth-first search)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

너비 우선 탐색(BFS)

그래프 내 모든 정점을 탐색하는 방법의 하나이다.
시작 정점으로부터 가까운 정점에서 먼 정점 순으로 방문하게 된다.
O(V + E) 시간에 수행된다.

1. 시작 정점 v를 큐에 삽입한다.
2. 큐가 비어있지 않은 동안 반복한다.
3. 큐에서 정점 1개를 꺼낸다.
4. 아직 방문하지 않았다면 방문하고, 이미 방문했다면 2로 돌아간다.
5. 꺼낸 정점을 방문했다고 표시한다.
6. 꺼낸 정점에 연결된 정점들 중 방문하지 않은 정점들을 큐에 삽입한다.
7. 2로 돌아간다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>

using namespace std;

template <typename T>
struct Edge
{
    unsigned src;
    unsigned dst;
    T weight;
};

template <typename T>
class Graph
{
private:
    unsigned V;
    vector<Edge<T>> edge_list;

public:
    // N개의 정점으로 구성된 그래프
    Graph(unsigned N) : V(N) {}

    // 정점 개수 반환
    unsigned vertices() const { return V; }

    // 간선 리스트 반환
    vector<Edge<T>>& edges() const { return edge_list; }

    // v가 출발지인 모든 간선을 반환
    vector<Edge<T>> edges(unsigned v) const
    {
        vector<Edge<T>> edges_from_v;

        copy_if(edge_list.begin(), edge_list.end(), back_inserter(edges_from_v), [v](const Edge<T>& e) { return e.src == v; });

        return edges_from_v;
    }

    void add_Edge(Edge<T>&& e)
    {
        if (1 <= e.src && e.src <= V && 1 <= e.dst && e.dst <= V)
            edge_list.emplace_back(e);
        else
            cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
    }

    template <typename U>
    friend ostream& operator << (ostream& os, const Graph<U>& G);
};

template <typename U>
ostream& operator << (ostream& os, const Graph<U>& G)
{
    for (unsigned i = 1; i < G.vertices(); ++i)
    {
        os << i << ":\t";

        for (Edge<U>& e : G.edges(i))
            os << "{" << e.dst << ": " << e.weight << "}, ";

        os << endl;
    }

    return os;
}

template <typename T>
Graph<T> create_reference_graph()
{
    Graph<T> G(9);

    map<unsigned, vector<pair<unsigned, T>>> edge_map;
    edge_map[1] = {{2, 0}, {5, 0}};
    edge_map[2] = {{1, 0}, {5, 0}, {4, 0}};
    edge_map[3] = {{4, 0}, {7, 0}};
    edge_map[4] = {{2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0}};
    edge_map[5] = {{1, 0}, {2, 0}, {4, 0}, {8, 0}};
    edge_map[6] = {{4, 0}, {7, 0}, {8, 0}};
    edge_map[7] = {{3, 0}, {6, 0}};
    edge_map[8] = {{4, 0}, {5, 0}, {6, 0}};

    for (auto& i : edge_map)
        for (pair<unsigned, T>& j : i.second)
            G.add_Edge(Edge<T>{i.first, j.first, j.second});

    return G;
}

template <typename T>
vector<unsigned> breadth_first_search(const Graph<T>& G, unsigned start)
{
    set<unsigned> visited;          // 방문한 정점
    vector<unsigned> visit_order;   // 방문 순서
    queue<unsigned> que;

    que.push(start);

    while (!que.empty())
    {
        unsigned current_vertex = que.front(); que.pop();

        if (visited.find(current_vertex) == visited.end())
        {
            visited.insert(current_vertex);
            visit_order.emplace_back(current_vertex);

            for (Edge<T>& e : G.edges(current_vertex))
                if (visited.find(e.dst) == visited.end())
                    que.push(e.dst);
        }
    }

    return visit_order;
}

void main()
{
    using T = unsigned;

    Graph<T> G = create_reference_graph<T>();
    cout << "[입력 그래프]" << endl;
    cout << G << endl;

    // 1번 정점부터 BFS 수행
    vector<T> bfs_visit_order = breadth_first_search<T>(G, 1);

    // 방문 순서 출력
    cout << "[BFS 방문 순서]" << endl;
    for (T v : bfs_visit_order)
        cout << v << endl;
}

 

출력

[입력 그래프]
1:      {2: 0}, {5: 0},
2:      {1: 0}, {5: 0}, {4: 0},
3:      {4: 0}, {7: 0},
4:      {2: 0}, {3: 0}, {5: 0}, {6: 0}, {8: 0},
5:      {1: 0}, {2: 0}, {4: 0}, {8: 0},
6:      {4: 0}, {7: 0}, {8: 0},
7:      {3: 0}, {6: 0},
8:      {4: 0}, {5: 0}, {6: 0},

[BFS 방문 순서]
1
2
5
4
8
3
6
7