그래프(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(깊이 우선 탐색)과 같은 방법을 사용할 수 있다.