Graph Algorithm - BFS

thewoowon·2022년 3월 2일
1

Algorithm

목록 보기
1/10

안녕하세요. 우원입니다.

넓이 우선 탐색에 대해 코드를 작성하고 분석하겠습니다.

#include <string>
#include <vector>
#include <iostream>
#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
{
public:
    Graph(unsigned N) : V(N) {}

    auto vertices() const { return V; }

    auto& edges() const { return edge_list; }

    auto edges(unsigned v) const
    {
        vector<Edge<T>> edges_from_v;
        for (auto& e : edge_list)
        {
            if (e.src == v)
                edges_from_v.emplace_back(e);
        }

        return edges_from_v;
    }
    void add_edge(Edge<T>&& e)
    {
        // 에지 양 끝 정점 ID가 유효한지 검사
        if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
            edge_list.emplace_back(e);
        else
            cerr << "에러 : 유효 범위를 벗어난 정점!" << endl;
    }

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

private:
    unsigned V;
    vector<Edge<T>> edge_list;

};

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

        os << endl;
    }

    return os;
}

template <typename T>
auto 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 (auto& j : i.second)
            G.add_edge(Edge<T>{i.first, j.first, j.second});

    return G;
}


template <typename T>
auto breadth_first_search(const Graph<T>& G, unsigned start)
{
    queue<unsigned> queue;
    set<unsigned> visited;
    vector<unsigned> visit_order;
    queue.push(start);

    while (!queue.empty())
    {
        auto current_vertax = queue.front();
        queue.pop();

        //현재 정점을 이전에 방문하지 않았다면
        if (visited.find(current_vertax) == visited.end())
        {
            visited.insert(current_vertax);
            visit_order.push_back(current_vertax);

            for (auto& e : G.edges(current_vertax))
            {
                // 인접한 정점 중에서 방문하지 않은 정점이 있다면 큐에 추가
                if (visited.find(e.dst) == visited.end())
                {
                    queue.push(e.dst);
                }
            }
        }
    }
    return visit_order;
}

int main()
{
    using T = unsigned;
    //그래프 객체 생성
    auto G = create_reference_graph<T>();
    cout << "[입력 그래프]" << endl;
    cout << G << endl;

    //1번 정점부터 BFS 실행 & 방문 순서 출력
    cout << "[BFS 방문 순서]" << endl;
    auto bfs_visit_order = breadth_first_search(G, 1);
    for (auto v : bfs_visit_order)
        cout << v << endl;
}

그래프 알고리즘으로 가장 기본이 되는 알고리즘입니다.
그래프에서 넓이란 같은 깊이(Depth)에 있다는 의미입니다.
일반 트리나 이진 트리 모두에서 사용 할 수 있고
queue를 사용해서 구현하는 특징이 있습니다.

가장 먼저 노드를 연결하는 Edge와 Graph 클래스를 선언합니다.
unsigned는 unsigned int와 동일합니다.
src(source) - 출발지, dst(destination) - 목적지이며
각각의 에지는 가중치(weight)를 가지고 있습니다.

Graph 클래스는 내부에 생성자가 정의되어 있습니다.
private 내부 변수 V를 초기화합니다.
멤버 함수 끝의 const는 해당 멤버 함수 내에서는 모든 멤버 변수를 상수화한다는 약속입니다.
비록 변수로 선언되더라도 멤버 함수내에서 연산 시,
객체의 멤버 변수 재할당이나 초기화를 제한할 필요가 있을 때 사용됩니다.

emplace와 emplace_back 삽입 동작 시 불필요한 복사를 피하고 메모리의 낭비를 줄여줍니다.
&& 참조는 r-value에 별명을 붙여 l-value로 만들어 줍니다.
각 노드의 시작과 끝이 입력된 총 노드 수보다 작거나 같고 1보다 크거나 같은지 검사합니다.

연산자 오버로딩으로 Graph가 입력으로 들어갈 때,
그래프의 노드를 순서대로 돌며 번호와 가중치를 출력해줍니다.

BFS는 재귀적으로 동작하지 않습니다.
주어진 노드와 하나의 에지로 연결된 노드들만 반환 받아
반복문으로 방문한 뒤 방문 여부를 반드시 체크합니다.
방문 체크가 없을 시, 무한 루프에 빠질 수 있습니다.

해당 코드를 콘솔 프로젝트에 입력 후 중단점을 설정한 후 리뷰합니다.

[입력 그래프]
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

위의 내용이 콘솔에 출력됩니다.
감사합니다.

profile
요람에서 코드까지

0개의 댓글