[자료구조] 그래프

그래프

• 노드로 이루어진 자료구조.
• 순환 종속성 문제(cyclic dependency)를 해결하기 위해 사용하는 자료구조.

그래프의 예시

• 다음과 같은 네트워크 형식을 그래프의 예시로 나타낼 수 있음.
• 트리에서와 같이 데이터가 저장된 부분을 Node라고 하며, 노드 사이를 잇는 선을 Edge라고 함. 현재 이 그래프에서는 양방향성 그래프이며, 순환성 그래프이다.

그래프 구현

#include<iostream>
#include<vector>

using namespace std;

// enum class로 각 도시를 숫자로 나타낼 수 있게 함.
enum class city : int
{
    MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY
};

// city class에 << 연산을 추가.
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
{
    // 2차원 vector 생성.
    vector<vector<int>> data;

    graph(int n)
    {
        // 그래프 선언 시, 배열의 크기를 6으로 만들고, 각 배열의 값을 -1로 초기화
        data.reserve(n);
        vector<int> row(n);
        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)
    {
        cout << "에지 추가: " << c1 << "-" << c2 << "=" << dis << 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)
    {
        cout << "에지 삭제: " << c1 << "-" << c2 << endl;

        auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);
        // 초기값이 -1이었으므로, 삭제 시 -1로 값 설정.
        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);
}

결과 값

정상적으로 잘 작동하는 모습.