Data Structure/C++ STL

[C++ STL] 2.6 그래프(graph)

lumana 2024. 6. 21. 02:08

그래프(graph)

  • 트리는 원형 또는 순환적인 종속성을 표현할 수 없다.
    • 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에
      • 도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.
  • 이러한 경우에는 그래프(graph) 구조를 사용해야 한다

그래프 구분 - weight

  • 그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.
    • 도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.
      • 이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.
        • 이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.
  • 에지에 가중치 또는 더 많은 정보를 부여할 수 있다.
    • 도로망에서 에지에 노드와 노드 사이의 거리를 저장할 수 있다.
      • 이러한 형태의 그래프를 가중 그래프(weighted graph) 라고 한다
    • 최단 거리 경로 탐색 같은 문제에서 이 그래프를 활용할 수 있다.

그래프 구분 - 방향성

  • 그래프는 방향성이 있는 그래프와 방향성이 없는 그래프로 구분할 수 있다.
  • 무방향 그래프(undirected graph)는 에지가 양방향임을 의미한다.
    • 양방향이라 함은 대칭적인, 또는 상호 교환적인 속성을 나타낸다
  • 이와 반대되는 개념으로는 방향 그래프(directed graph)가 있다.
    • 어떤 도로가 일방통행으로 제한되어 있는 경우를 생각해보자
    • 방향 그래프에서 양방향 에지를 표현하려면, A->B, B->A 두 개의 에지를 사용해야 한다
  • 무방향 그래프의 구조와 순회방법은 방향 그래프에도 적용할 수 있다.
    • 다만 그래프에 에지를 추가하는 방법만 달라짐

그래프 표현

  • 그래프는 순환적 에지를 가질 수 있고, 특정 노드에서 다른 노드로 이동하는 방법이 여러 개 있을 수 있다.
    • 따라서 각 노드를 고유하게 식별해야 한다.
    • 이를 위해 각 노드에 고유한 ID를 부여할 수 있다.
  • 그래프의 데이터를 표현하기 위해 반드시 트리의 노드 같은 구조를 사용해야 하는 것은 아니다.
    • 실제로 STL 컨테이너를 이용하여 그래프를 표현할 수 있다.

인접 행렬로 그래프 표현하기

  • 노드가 N개 있을 경우, 이 그래프는 N X N 크기의 2차원 배열로 표현할 수 있다.
  • 이 배열에서 특정 원소는 해당 원소 인덱스에 해당하는 노드 사이의 거리를 표현한다.
    • data[1][2]는 1번 노드와 2번 노드를 잇는 에지의 가중치를 나타낸다
  • 이러한 방식으로 그래프를 표현하는 방법을 인접 행렬(adjacency matrix)라고 한다
  • 두 노드 사이에 에지가 존재하지 않으면 해당 원소에 -1을 설정한다

Example) 인접 행렬로 도시 네트워크 그래프 구성하기

#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;
    }
};

using namespace std;

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;
}
  • 벡터의 벡터를 이용하여 데이터를 저장했다.
  • 노드 개수가 V라면, 전체 V X V 크기의 메모리 공간을 사용하게 된다

인접 리스트로 그래프 표현하기

  • 행렬을 이용하여 그래프를 표현할 때 가장 큰 문제는, 노드 개수의 제곱에 비례하는 메모리를 사용한다는 점이다
    • 행렬을 사용할 경우 두 노드가 서로 연결되어 있지 않더라도 모든 노드 사이의 에지 정보를 저장해야 한다
  • 대신 각 노드에 직접 연결되어 있는 노드의 ID만 저장하는 방식으로 그래프를 표현할 수 있다.
    • 이러한 방식을 인접 리스트(adjacency list)라고 한다

Example) 인접 리스트로 도시 네트워크 그래프 구성하기

#include <iostream>
#include <vector>
#include <algorithm>

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<std::pair<int, int>>> data;

    graph(int n)
    {
        data = std::vector<std::vector<std::pair<int, int>>>(n, std::vector<std::pair<int, int>>());
    }

    // 에지 추가 함수로 두 개의 도시와 소이 사이의 거리(가중치)를 인자로 받음
    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].push_back({n2, dis});
        data[n2].push_back({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);

        std::remove_if(data[n1].begin(), data[n1].end(), [n2](const auto& pair) {
            return pair.first == n2;
        });
        std::remove_if(data[n2].begin(), data[n2].end(), [n1](const auto& pair) {
            return pair.first == n1;
        });
    }
};

using namespace std;

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;
}
  • 각 노드에 인접한 노드를 리스트에 저장하기 때문에 인접 리스트라고 한다
  • 데이터 저장을 위해 벡터의 벡터를 사용한다.
  • 다만 안쪽 벡터의 크기가 전체 노드 개수가 아니라 해당 노드에 연결된 노드 개수와 같다.
    • 인접 리스트에 의한 그래프 표현은 전체 에지 개수 E에 비례한 크기의 메모리를 사용한다.
  • 그래프를 탐색해야 하는 경우에는 BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색)과 같은 방법을 사용할 수 있다.
    • 알고리즘 파트에서 따로 다룰 예정

'Data Structure > C++ STL' 카테고리의 다른 글

[C++ STL] std::pair  (0) 2024.06.30
[C++ STL] 3.4 C++ 해시 테이블  (0) 2024.06.23
[C++ STL] 2.5 힙(Heap)  (0) 2024.06.21
[C++ STL] 1.8 컨테이너 어댑터(Container Adaptor)  (0) 2024.06.15
[C++ STL] 1.7 std::dequeue  (0) 2024.06.15