그래프(Graph)

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

 

 

트리의 단점

• 계층적 구조를 표현할 수 있는 반면 순환적인 종속성을 표현할 수 없다.

 

그래프

• 순환 구조를 표현할 수 있다.
  도시의 도로망, 항공 네트워크 등
• 정점(Vertex)과 정점 사이를 연결하는 간선(Edge)으로 구성된다.
• 각 정점은 연결된 다른 정점들의 정보를 유지해야 한다.
  인접 행렬(Adjacency Matrix) 혹은 인접 리스트(Adjacency list)로 관리한다.

 

인접 행렬과 인접 리스트

• 인접 행렬은 삽입/삭제 시 O(1) 시간 복잡도를 갖으나 O(n²) 공간 복잡도를 갖는다.
• 인접 리스트는 삽입 시 O(1), 삭제 시 O(n) 시간 복잡도를 갖으나 간선의 개수만큼의 공간만 필요로 한다.

 

 

그래프의 구분

• 순환 그래프(Cyclic Graph)
  내부에 루프가 존재하는 그래프이다.
• 비순환 그래프(Acyclic Graph)
  내부에 루프가 존재하지 않는 그래프이다.
• 가중 그래프(Weighted Graph)
  간선이 가중치를 갖는 그래프이다.
• 비가중 그래프(Unweighted Graph)
  간선이 가중치를 갖지 않는 그래프이다.
• 방향 그래프(Directed Graph)
  간선의 단방향 이동만 허용하는 그래프이다.
• 무방향 그래프(Undirected Graph)
  간선의 양방향 이동을 허용하는 그래프이다.

 

인접 행렬을 이용한 구현

 

#include <iostream>
#include <vector>

using namespace std;

enum class city : int
{
    MOSCOW,
    LONDON,
    SEOUL,
    SEATTLE,
    DUBAI,
    SYDNEY
};

ostream& operator<<(ostream& os, const city c)
{
    switch (c)
    {
    case city::MOSCOW:  os << "모스크바"; break;
    case city::LONDON:  os << "런던"; break;
    case city::SEOUL:   os << "서울"; break;
    case city::SEATTLE: os << "시애틀"; break;
    case city::DUBAI:   os << "두바이"; break;
    case city::SYDNEY:  os << "시드니"; break;
    }

    return os;
}

struct graph
{
    // 인접 행렬에 각 공항 사이의 거리를 저장한다.
    vector<vector<int>> data;

    graph(int n) : data(vector<vector<int>>(n, vector<int>(n, -1))) { }

    void addEdge(const city c1, const city c2, int dist)
    {
        int n1 = static_cast<int>(c1);
        int n2 = static_cast<int>(c2);

        data[n1][n2] = data[n2][n1] = dist;

        cout << "간선 추가: " << c1 << "-" << c2 << "=" << dist << endl;
    }

    void removeEdge(const city c1, const city c2)
    {
        int n1 = static_cast<int>(c1);
        int n2 = static_cast<int>(c2);

        data[n1][n2] = data[n2][n1] = -1;

        cout << "간선 삭제: " << c1 << "-" << c2 << endl;
    }
};

void 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);
}

 

출력

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

 

인접 리스트를 이용한 구현

 

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

using namespace std;

enum class city : int
{
    MOSCOW,
    LONDON,
    SEOUL,
    SEATTLE,
    DUBAI,
    SYDNEY
};

ostream& operator<<(ostream& os, const city c)
{
    switch (c)
    {
    case city::MOSCOW:  os << "모스크바"; break;
    case city::LONDON:  os << "런던"; break;
    case city::SEOUL:   os << "서울"; break;
    case city::SEATTLE: os << "시애틀"; break;
    case city::DUBAI:   os << "두바이"; break;
    case city::SYDNEY:  os << "시드니"; break;
    }

    return os;
}

struct graph
{
    // 인접 리스트에 인정합 공항의 ID와 거리를 저장한다.
    vector<vector<pair<int, int>>> data;

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

    void addEdge(const city c1, const city c2, int dist)
    {
        int n1 = static_cast<int>(c1);
        int n2 = static_cast<int>(c2);

        data[n1].push_back({n2, dist});
        data[n2].push_back({n1, dist});

        cout << "간선 추가: " << c1 << "-" << c2 << "=" << dist << endl;
    }

    void removeEdge(const city c1, const city c2)
    {
        int n1 = static_cast<int>(c1);
        int n2 = static_cast<int>(c2);

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

        cout << "간선 삭제: " << c1 << "-" << c2 << endl;
    }
};

void 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);
}

 

출력

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