그래프의 표현 방법은 총 세가지가 존재한다.
- 인접 행렬
- 인접 리스트
- 간선 리스트
대부분의 경우에는 인접 리스트를 사용하고, 부득이한 경우에는 간선 리스트를 사용한다. 인접행렬은 필요없는 공간의 소모가 많기 때문에 잘 사용하지 않는다.
그래프를 저장할 때는 두 가지 정보를 저장하게 된다.
1. 정점 (V)
개수만 저장하면 된다. 보통 1 ~ V로 주어지며, index로 이용하게 된다.
2. 간선 (E)
어떤 간선이 있었는지를 저장하면 된다. E개의 간선을 그냥 배열에 때려넣어도 되지만, 간선을 저장한다는 것의 의미는 어떤 정점과 연결된 간선을 찾을 수 있다는 의미이다.
인접 행렬
정점의 개수를 V개라고 했을 때, V*V 크기의 이차원 배열을 이용한다.
간선의 가중치가 존재하지 않을 때
A[i][j] = 1 (i -> j 간선이 존재할 때)
A[i][j] = 0 (i -> j 간선이 존재하지 않을 때)
```
```cpp
#include <iostream>
using namespace std;
int main()
{
int v, e;
int g[v + 1][v + 1];
for (int i = 0; i < e; i++)
{
int x, y;
cin >> x >> y;
// 양방향 그래프일 때
g[x][y] = g[y][x] = 1;
// 방향 그래프일 때
g[x][y] = 1;
}
}간선의 가중치가 존재할 때
w >= 0 인 경우
A[i][j] = w (i -> j 간선이 존재할 때)
A[i][j] = 0 (i -> j 간선이 존재하지 않을 때)w가 정수 범위인 경우
인접행렬 2개를 사용해야 한다.
- 간선이 존재하는지 여부를 알려주는 인접행렬
// A : 간선이 존재하는지를 알려주는 인접행렬 A[i][j] = 1 (i -> j 간선이 존재할 때) A[i][j] = 0 (i -> j 간선이 존재하지 않을 때) - 간선의 가중치를 알려주는 인접행렬
// B : 간선의 가중치를 알려주는 인접행렬 B[i][j] = w
인접 리스트
linked-list를 이용하여 구현한다. 굳이 linked-list를 사용하는 이유는 어떤 노드와 연결된 정점이 정확하게 몇 개인지 모르기 때문 이다.
인접 행렬은 i -> j 의 경로에서 서로 다른 가중치를 가진 여러 간선을 구분하여 저장할 수 없다.
linked-list를 직접 구현하려면 시간이 오래 걸리기 때문에, 주로 vector와 같이 길이를 변경할 수 있는 배열을 이용하여 구현한다.
간선의 가중치가 존재하지 않을 때
graph[i] -> i에 연결된 edge의 집합
ex) graph[1] = 5 는 edge (1,5)를 의미한다
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> graph[n+1]; // node 번호가 1 ~ n 일 경우
for(int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
graph[u].push_back(v);
// 양방향 그래프일 경우 양쪽에 저장
// graph[v].push_back(u);
}
}간선의 가중치가 존재할 때
graph[i] -> i에 연결된 edge의 집합
graph[1] = pair(5, 3) 은 1 -> 5 의 edge가 존재하고, w = 3임을 의미
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<pair<int,int>> graph[n+1];
for(int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back(make_pair(v, w));
// 양방향 그래프일 경우 양쪽에 저장
// graph[v].push_back(make_pair(u, w));
}
}인접 행렬과 인접 리스트의 공간 복잡도
| 구분 | 공간복잡도 |
|---|---|
| 인접 행렬 | O(V^2) |
| 인접 리스트 | O(E) |
우리가 주로 다룰 그래프는 E < V 이므로, 인접리스트를 사용하여 그래프를 표현하는 것이 효과적이다.
간선 리스트
인접 리스트와 인접 행렬을 모두 사용할 수 없는 경우 간선 리스트를 사용한다. STL, Array collection 등을 사용할 수 없는 경우가 여기에 해당된다.
하나의 배열을 이용하여 모든 간선을 저장하고, 누적합을 저장한 다른 배열로 한 정점의 간선이 저장된 index의 범위를 알려주도록 한다.
아래와 같이 구현할 경우, i번 정점과 연결된 간선은 E배열에서 index가 cnt[i-1]번 부터 cnt[i]-1 인 것에 해당한다.
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
// E[i][0] = i번째 간선의 시작 정점
// E[i][1] = i번째 간선의 도착 정점
int E[m][2];
int cnt[n];
for(int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
E[i][0] = u;
E[i][1] = v;
}
// E 배열을 E[i][0] (시작 정점)을 기준으로 정렬
// 각 정점에 연결되어 있는 edge의 개수 세기
for(int i = 0; i < m; i++)
cnt[e[i][0]] += 1;
// cnt의 누적합 구하기
for(int i = 1; i <= n; i++)
cnt[i] = cnt[i-1] + cnt[i];
}출처
백준 알고리즘 인강
