2-3 그래프

트리는 계층적 데이터를 표현하는 좋은 방법이지만, 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 원형 또는 순환적인 종속성을 표현할 수 없다. 

 

그러나 실생활에서 순환 구조를 사용하여 표현해야 하는 시나리오도 많이 존재한다. 

예를 들어 도로망을 생각해보면, 특정 장소(노드)에서 다른 장소로 이동하기 위한 다양한 경로가 존재할 수 있다. 

이러한 경우에는 그래프(graph) 구조를 사용하는 것이 더욱 바람직하다. 

 

그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다. 

도로망을 예로 들면 각각의 노드(장소)에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다. 

이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있으며, 이러한 그래프를 비가중 그래프(unweighted graph)라고 한다. 

 

에지에 가중치(weight) 또는 더 많은 정보를 부여할 수도 있다. 예를 들어 도로망을 구성할 때 각각의 에지(도로)에 노드(장소)와 노드 사이의 거리를 저장할 수 있다. 이러한 형태의 그래프를 가중 그래프(weighted graph)라고 한다. 

 

도로망을 가중 그래프 형태로 표현함으로써 특정 장소에서 다른 장소로 이동하는 최단 거리 경로 탐색 같은 문제에서 이 그래프를 활용할 수 있다. 

 

그래프는 방향성이 있는 그래프와 방향성이 없는 그래프로 구분할 수 있다.

무방향 그래프(undirected graph)는 에지가 양방향임을 의미한다. 

양방향이라 함은 대칭적인, 또는 상호 교환적인 속성을 나타낸다. 

 

만약 어떤 도로가 일방통행으로 제한되어 있다면 이때는 방향 그래프(directed graph)를 사용해야 한다. 

 

그래프는 순환적 에지를 가질 수 있고 특정 노드에서 다른 노드로 이동하는 방법이 여러 개 있을수 있으므로 각 노드를 고유하게 식별해야 한다. 이를 위해 각 노드에 고유한 ID를 부여할 수 있다. 

그래프의 데이터를 표현하기 위해 반드시 트리의 노드 같은 구조를 사용해야 하는 것은 아니다. 

실제로 STL 컨테이너를 이용하여 그래프를 표현할 수 있다. 

 

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

노드의 집합이 있고, 노드끼리 서로 연결될 수 있다고 가정하자. 

노드가 N개 있을 경우, 이 그래프는 N X N 크기의 2차원 배열로 표현할 수 있다. 

이 배열에서 특정 원소는 해당 원소 인덱스에 해당하는 노드 사이의 가중치를 표현한다.

즉, data[1][2]는 1번 노드와 2번 노드를 잇는 에지의 가중치를 나타낸다. 이러한 방식으로 그래프를 표현하는 방법을 인접 행렬(adjacency matrix)라고 한다. 

두 노드 사이에 에지가 존재하지 않으면 해당 원소에 -1을 설저한다. 

 

#include <iostream>
#include <vector>

//enum 클래스를 이용하여 도시 이름을 저장
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)
    {
    	//reserve(n) : vector의 용량을 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)
    {
    	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)
    {
    	auto n1 = static_cast<int>(c1);
        auto n2 = static_cast<int>(c2);
        data[n1][n2] = -1;
        data[n2][n1] = -1;
    }
    };

 

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

행렬을 이용하여 그래프를 표현할 때의 가장 큰 문제점은 노드 개수의 제곱에 비례하는 메모리를 사용한다는 점이다. 

노드 개수가 증가함에 따라 메모리 사용량은 크게 늘어난다. 그러므로 메모리를 좀 더 적게 사용하는 방법을 생각해봐야 한다. 

 

어느 그래프에서나 정해진 수의 노드가 있고, 각 노드에서 연결될 수 있는 노드의 최대 개수는 전체 노드 개수와 같다. 

행렬을 사용할 경우, 두 노드가 서로 연결되어 있지 않더라도 모든 노드 사이의 에지 정보를 저장해야 한다. 

이러한 방식 대신 각 노드에 직접 연결되어 있는 노드의 ID만 저장하는 방식으로 그래프를 표현할 수 있다. 

이러한 방식을 인접 리스트(adjacency list)라고 한다. 

 

#include <iostream>
#include <vecotr>
#include <algorithm>

//enum 클래스를 이용하여 도시 이름을 저장
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
{
	//pair : 두 개체를 단일 개체로 처리하는 기능을 제공하는 구조체
	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)
    {
    	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)
    {
    	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;
        });
    }
};

각 노드에 인접한 노드를 리스트로 저장하기 때문에 인접 리스트라고 한다. 

이 방법은 앞서 설명한 인접 행렬 방법과 마찬가지로 데이터 저장을 위해 벡터의 벡터를 사용한다. 

다만 안쪽 벡터의 크기가 전체 노드 개수가 아니라 해당 노드에 연결된 노드 개수와 같다. 

addEdge() 함수 구현을 보면 에지 끝에 있는 두 노드에 대해 각각 에지 연결을 설정하는 것을 확인할 수 있다.

인접 리스트에 의한 그래프 표현은 전체 에지 개수 E에 비례한 크기의 메모리를 사용한다.