알고리즘/그래프 이론
[1][그래프 이론] - 그래프 표현 및 정의
Source
2021. 1. 26. 19:58
그래프(Graph) 란?
그래프는 어떤 자료나 개념을 각각의 정점들(vertex)의 집합 V와 그 정점들을 이어주는 간선들(edge)의 집합 E로 구성된 자료 구조이다.
이러한 그래프는 크게 두가지로 표현이 가능하다.
1. 인접 리스트 표현
2. 인접 행렬 표현
1. 인접 리스트 표현
첫번째로 그래프를 표현할 수 있는 방법은 인접 리스트 이다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<vector<int>> v;
for(int i=0;i<4;i++){
v.push_back(vector<int>());
}
v[0].push_back(1);
v[0].push_back(2);
v[1].push_back(0);
v[1].push_back(2);
v[1].push_back(3);
v[2].push_back(0);
v[2].push_back(1);
v[2].push_back(3);
v[3].push_back(1);
v[3].push_back(2);
}
상단에 주어진 그래프를 표현하는 코드이다.
vector내에 int형을 가지는 vector를 포함하는 타입을 활용해서 각 정점마다 간선이 존재하는 정점들을 추가하여 구성하였다.
예를들어
v[2].push_back(1) 의 경우는 2번 정점에서 1번 정점으로 가는 간선이 존재하므로 추가해준것이고 결국
v[2] 는 0,1,3 을 가지는 벡터가 될것이고 이것은 2번 정점에서 0,1,3 정점으로 갈수 있다는 의미이다.
2. 인접 행렬 표현
두번째로 그래프를 표현할 수 있는 방법은 인접 행렬이다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int graph[4][4];
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
graph[i][j] = 0;
}
}
graph[0][1] = 1;
graph[0][2] = 1;
graph[1][0] = 1;
graph[1][2] = 1;
graph[1][3] = 1;
graph[2][0] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[3][1] = 1;
graph[3][2] = 1;
}
graph[i][j] 가 0이면 i 정점에서 j 정점으로 갈수있는 간선이 없다는 의미이고, 반대로 1이라면 간선이 존재한다는 의미이다.