그래프 표현 공부
그래프 표현 방법
- 그래프 알고리즘을 이해하기 위해서 그래프 표현 방법을 공부했습니다.
- 그래프를 표현하는 방법은 인접 행렬, 인접 리스트, 간선 리스트로 3가지가 있습니다.
- 이 글은 이 3가지 방법에 대해서 정리한 내용입니다.
인접 행렬
- 인접 행렬은 노드와 노드 사이의 관계를 행렬 형태로 표현하는 방법입니다.
- 2차원 배열로 표현하고 출발 노드를 행, 도착 노드를 열로 표현합니다.
- 노드 개수가 많은 경우 2차원 배열 선언을 못할 수 있기 때문에 노드의 개수에 따라 사용 여부를 적절히 판단해야 합니다.
가중치 없는 그래프 표현
- 가중치 없는 그래프는 노드와 노드가 연결된 표시를 1로 저장합니다.
- 1로 저장한 이유는 가중치가 없다는 것을 표현한 것 입니다.
가중치 있는 그래프 표현
- 가중치 있는 그래프는 노드와 노드가 연결된 표시를 가중치 값으로 저장합니다.
코드 구현
인접 행렬 표현
int mat1[5][5]; // 가중치 없는 그래프
int mat2[5][5]; // 가중치 있는 그래프
- 인접 행렬은 2차원 배열을 사용해서 표현했습니다.
- 가중치 없는 그래프와 가중치 있는 그래프 모두 동일한 자료 구조를 사용합니다.
노드와 노드 연결
// 가중치 없는 그래프 간선 연결
mat1[1][2] = 1;
mat1[2][1] = 1;
mat1[1][3] = 1;
mat1[3][1] = 1;
mat1[3][4] = 1;
mat1[4][3] = 1;
// 가중치 있는 그래프 간선 연결
mat2[1][2] = 2;
mat2[2][1] = 2;
mat2[1][3] = 3;
mat2[3][1] = 3;
mat2[3][4] = 1;
mat2[4][3] = 1;
- 변수명[출발 노드][도착 노드] = 가중치의 값 형태로 노드를 연결합니다.
전체 코드
#include <iostream>
using namespace std;
int mat1[5][5]; // 가중치 없는 그래프
int mat2[5][5]; // 가중치 있는 그래프
int main() {
// 가중치 없는 그래프 간선 연결
mat1[1][2] = 1;
mat1[2][1] = 1;
mat1[1][3] = 1;
mat1[3][1] = 1;
mat1[3][4] = 1;
mat1[4][3] = 1;
cout << "가중치 없는 그래프 표현\n";
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << mat1[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
// 가중치 있는 그래프 간선 연결
mat2[1][2] = 2;
mat2[2][1] = 2;
mat2[1][3] = 3;
mat2[3][1] = 3;
mat2[3][4] = 1;
mat2[4][3] = 1;
cout << "가중치 있는 그래프 표현\n";
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << mat2[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
return 0;
}
- 출력
가중치 없는 그래프 표현
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 0 1
0 0 0 1 0
가중치 있는 그래프 표현
0 0 0 0 0
0 0 2 3 0
0 2 0 0 0
0 3 0 0 1
0 0 0 1 0
인접 리스트
- 인접 리스트는 노드의 개수만큼 공간을 확복한 뒤에 각 노드를 기준으로 연결된 노드를 저장하는 방법입니다.
가중치 없는 그래프 표현
- 노드 리스트에 연결 노드를 저장하는 형태입니다.
가중치 있는 그래프 표현
- 노드 리스트에 연결 노드와 가중치를 저장하는 형태입니다.
코드 구현
인접 리스트 표현
vector<int> v1[5]; // 가중치 없는 그래프 표현
vector<pair<int, int>> v2[5]; // 가중치 있는 그래프 표현
- 인접 리스트는 vector를 사용해서 표현했습니다.
- 가중치 없는 그래프는 연결 노드 저장만 수행하기 때문에 정수형을 사용합니다.
- 가중치 있는 그래프는 연결 노드와 가중치를 저장하기 위해 pair를 사용합니다.
노드와 노드 연결
// 가중치 없는 그래프 간선 연결
v1[1].push_back(2);
v1[1].push_back(3);
v1[2].push_back(1);
v1[3].push_back(1);
v1[3].push_back(4);
v1[4].push_back(3);
// 가중치 있는 그래프 간선 연결
v2[1].push_back({ 2,2 });
v2[1].push_back({ 3,3 });
v2[2].push_back({ 1,2 });
v2[3].push_back({ 1,3 });
v2[3].push_back({ 4,1 });
v2[4].push_back({ 3, 1});
- 가중치 없는 그래프는 출발 노드 영역에 연결 노드를 추가합니다.
- 가중치 있는 그래프는 출발 노드 영역에 연결 노드와 가중치를 추가합니다.
전체 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> v1[5]; // 가중치 없는 그래프 표현
vector<pair<int, int>> v2[5]; // 가중치 있는 그래프 표현
int main() {
// 가중치 없는 그래프 간선 연결
v1[1].push_back(2);
v1[1].push_back(3);
v1[2].push_back(1);
v1[3].push_back(1);
v1[3].push_back(4);
v1[4].push_back(3);
cout << "가중치 없는 그래프 표현\n";
int idx = 0;
for(vector<int> node:v1){
cout << idx << "번 노드: ";
for (int connect : node) {
cout << connect << " ";
}
idx++;
cout << "\n";
}
cout << "\n";
// 가중치 있는 그래프 간선 연결
v2[1].push_back({ 2,2 });
v2[1].push_back({ 3,3 });
v2[2].push_back({ 1,2 });
v2[3].push_back({ 1,3 });
v2[3].push_back({ 4,1 });
v2[4].push_back({ 3, 1});
cout << "가중치 있는 그래프 표현\n";
idx = 0;
for (vector<pair<int,int>> node : v2) {
cout << idx << "번 노드: ";
for (pair<int,int> connect : node) {
cout <<"{" << connect.first << " " << connect.second << "} ";
}
idx++;
cout << "\n";
}
cout << "\n";
return 0;
}
- 출력
가중치 없는 그래프 표현
0번 노드:
1번 노드: 2 3
2번 노드: 1
3번 노드: 1 4
4번 노드: 3
가중치 있는 그래프 표현
0번 노드:
1번 노드: {2 2} {3 3}
2번 노드: {1 2}
3번 노드: {1 3} {4 1}
4번 노드: {3 1}
간선 리스트
- 간선 리스트는 간선의 정보만을 저장하는 방법입니다.
- 노드 중심 알고리즘에는 사용하기 쉽지 않습니다.
- 벨만 포드, 크루스칼 알고리즘에 활용됩니다.
가중치 없는 그래프 표현
- 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 열 2개면 충분합니다.
가중치 있는 그래프 표현
- 가중치가 있는 그래프는 배열의 열 3개로 늘리면 됩니다.
- 크루스칼 알고리즘을 사용할 때 가중치 기준으로 정렬하는 과정이 필요하기 때문에 (가중치, 출발 노드, 도착 노드)로 표현합니다.
코드 구현
간선 리스트 표현
vector<array<int, 2>> v1; // 가중치 없는 그래프 표현
vector<array<int, 3>> v2; // 가중치 있는 그래프 표현
- 간선 리스트는 vector를 사용해서 표현했습니다.
- 가중치 없는 그래프는 출발 노드와 도착 노드를 저장하기 위해 크기가 2인 array를 사용합니다.
- 가중치 있는 그래프는 출발 노드와 도착 노드 그리고 가중치를 저장하기 위해 크기가 3인 array를 사용합니다.
노드와 노드 연결
// 가중치 없는 그래프 간선 연결
v1.push_back({ 1,2 });
v1.push_back({ 2,1 });
v1.push_back({ 1,3 });
v1.push_back({ 3,1 });
v1.push_back({ 3,4 });
v1.push_back({ 4,3 });
// 가중치 없는 그래프 간선 연결
v2.push_back({ 2,1,2 });
v2.push_back({ 2,2,1 });
v2.push_back({ 3,1,3 });
v2.push_back({ 3,3,1 });
v2.push_back({ 1,3,4 });
v2.push_back({ 1,4,3 });
- 가중치 없는 그래프는 출발 노드와 도착 노드를 저장합니다.
- 가중치 있는 그래프는 가중치, 출발 노드, 도착 노드를 저장합니다.
- 가중치가 첫번째 원소로 설정한 이유는 크루스칼 알고리즘에서 가중치를 기준으로 정렬을 하는데 기본적으로 첫번째 원소를 기준으로 정렬하기 때문에 편의상 첫번째 원소에 가중치를 설정했습니다.
전체 코드
#include <iostream>
#include <vector>
#include <array>
using namespace std;
vector<array<int, 2>> v1; // 가중치 없는 그래프 표현
vector<array<int, 3>> v2; // 가중치 있는 그래프 표현
int main() {
// 가중치 없는 그래프 간선 연결
v1.push_back({ 1,2 });
v1.push_back({ 2,1 });
v1.push_back({ 1,3 });
v1.push_back({ 3,1 });
v1.push_back({ 3,4 });
v1.push_back({ 4,3 });
cout << "가중치 없는 그래프 표현\n";
for (array<int, 2> e : v1) {
cout << "{" << e[0] << " " << e[1] << "}\n";
}
cout << "\n";
// 가중치 없는 그래프 간선 연결
v2.push_back({ 2,1,2 });
v2.push_back({ 2,2,1 });
v2.push_back({ 3,1,3 });
v2.push_back({ 3,3,1 });
v2.push_back({ 1,3,4 });
v2.push_back({ 1,4,3 });
cout << "가중치 있는 그래프 표현\n";
for (array<int, 3> e : v2) {
cout << "{" << e[0] << " " << e[1] << " " << e[2] << "}\n";
}
return 0;
}
- 출력
가중치 없는 그래프 표현
{1 2}
{2 1}
{1 3}
{3 1}
{3 4}
{4 3}
가중치 있는 그래프 표현
{2 1 2}
{2 2 1}
{3 1 3}
{3 3 1}
{1 3 4}
{1 4 3}