[C++] 인접 행렬을 이용하여 그래프 구현하기

인접 행렬을 이용하여 그래프 구현하기

서론

인접 행렬(Adjacent Matrix)을 이용하여 그래프(Graph)를 구현해보자.

 

코드

#include <iostream>
#include <vector>
 
enum class city : int {
    MOSCOW,
    LONDON,
    SEOUL,
    SEATTLE,
    DUBAI,
    SYDNEY
};
 
std::ostream& operator<<(std::ostream& os, const city c) {
    switch (c) {
        case city::LONDON:
            os << "런던";
            return os;
        case city::MOSCOW:
            os << "모스크바";
            return os;
        case city::SEOUL:
            os << "서울";
            return os;
        case city::SEATTLE:
            os << "시애틀";
            return os;
        case city::DUBAI:
            os << "두바이";
            return os;
        case city::SYDNEY:
            os << "시드니";
            return os;
        default:
            return os;
    }
}
 
struct graph {
    std::vector<std::vector<int>> data;
 
    graph(int n) {
        data.reserve(n);
        std::vector<int> row(n);
        std::fill(row.begin(), row.end(), -1);
 
        for (int i = 0; i < n; i++) {
            data.push_back(row);
        }
    }
 
    void addEdge(const city c1, const city c2, int dis) {
        std::cout << "에지 추가: " << c1 << "-" << c2 << "=" << dis << std::endl;
 
        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);
        data[n1][n2] = dis;
        data[n2][n1] = dis;
    }
 
    void removeEdge(const city c1, const city c2) {
        std::cout << "에지 삭제: " << c1 << "-" << c2 << std::endl;
 
        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);
        data[n1][n2] = -1;
        data[n2][n1] = -1;
    }
};
 
int main() {
    graph g(6);
 
    g.addEdge(city::LONDON, city::MOSCOW, 2500);
    g.addEdge(city::LONDON, city::SEOUL, 9000);
    g.addEdge(city::LONDON, city::DUBAI, 5500);
    g.addEdge(city::SEOUL, city::MOSCOW, 6600);
    g.addEdge(city::SEOUL, city::SEATTLE, 8000);
    g.addEdge(city::SEOUL, city::DUBAI, 7000);
    g.addEdge(city::SEOUL, city::SYDNEY, 8000);
    g.addEdge(city::SEATTLE, city::MOSCOW, 8400);
    g.addEdge(city::SEATTLE, city::SYDNEY, 12000);
    g.addEdge(city::DUBAI, city::SYDNEY, 1200);
 
    g.addEdge(city::SEATTLE, city::LONDON, 8000);
    g.removeEdge(city::SEATTLE, city::LONDON);
 
    return 0;
}

결과 확인

에지 추가: 런던-모스크바=2500
에지 추가: 런던-서울=9000
에지 추가: 런던-두바이=5500
에지 추가: 서울-모스크바=6600
에지 추가: 서울-시애틀=8000
에지 추가: 서울-두바이=7000
에지 추가: 서울-시드니=8000
에지 추가: 시애틀-모스크바=8400
에지 추가: 시애틀-시드니=12000
에지 추가: 두바이-시드니=1200
에지 추가: 시애틀-런던=8000
에지 삭제: 시애틀-런던