6장 그래프 - (2) 그래프의 표현

1. 그래프의 표현(Representation of Graph) - 인접행렬, 인접리스트, 간선리스트

- 아래와 같은 그래프는 정점이 6개, 간선이 8개 있다.

- 간선에 방향이 없기 때문에, 방향이 없는 그래프이다.

- 정점 : {1,2,3,4,5,6}

- 간선 : {(1,2),(1,5),(2,5),(2,3),(3,4),(2,4),(4,5),(4,6)}

2. 인접 행렬(Adjacency Matrix)

- 정점의 개수를 V라고 했을 때

- V * V 크기의 이차원 배열을 이용한다.

- A[i][j] = 1(i->j 간선이 있을 때), 0 없을 때

(예시1) - n개의 정점, m개의 간선, 가중치 없는 양방향 그래프

#include <iostream>

using namespace std;

int a[10][10];

int main(void){

int n,m; // n이 정점 개수, m이 간선 개수

cin >> n >> m;

for(int i=0;i<m;i++){

int u,v;

cin >> u >> v;

a[u][v]=a[v][u]=1;

}

return 0;

}

(예시2) - n개의 정점, m개의 간선, 가중치 있는 양방향 그래프

#include <iostream>

using namespace std;
int a[10][10];

int main(void){

int n,m;

cin >> n >> m;

for(int i=0;i<m;i++){

int u,v,w;

cin >> u >> v >> w;

a[u][v]=a[v][u]=w;

}

return 0;

}

3. 인접 리스트(Adjacency-list)

-링크드 리스트를 이용해서 구현한다.

- A[i] : i와 연결된 정점들을 링크드리스트로 포함하고 있음

위의 예로

A[1] : 2 5

A[2] : 1 3 4 5

A[3] : 2 4

A[4] : 2 3 5 6

A[5] : 1 2 4

A[6] : 4

- 링크드 리스트는 구현하는데 시간이 오래 걸리기 때문에, 주로 vector와 같이 길이를 변경할 수 있는 배열을 이용해서 구현한다.

(예시1) - n개의 정점, m개의 간선, 가중치 없는 양방향 그래프

#include <iostream>

#include <vector>

using namespace std;

vector<int> a[10];

int main(void){

int n,m;

cin >> n >> m;

for(int i=0;i<m;i++){

int u,v;

cin >> u >> v;

a[u].push_back(v);

a[v].push_back(u);

}

return 0;

}

(예시2) - n개의 정점, m개의 간선, 가중치 없는 양방향 그래프

#include <iostream>

#include <vector>

using namespace std;

int main(void){

int n,m;

cin >> n >> m;

vector<vector<int>> a(n+1);

for(int i=0;i<m;i++){

int u,v;

cin >> u >> v;

a[u].push_back(v);

a[v].push_back(u);

}

return 0;

}

(예시3) - n개의 정점, m개의 간선, 가중치 있는 양방향 그래프

#include <iostream>

#include <vector>

using namespace std;

vector<pair<int,int>> a[10];

int main(void){

int n,m;

cin >> n >> m;

for(int i=0;i<m;i++){

int u,v,w;

cin >> u >> v >> w;

a[u].push_back(make_pair(v,w);

a[v].push_back(make_pair(u,w);

}

return 0;

}

4. 공간 복잡도

-인접행렬 : O(V^2)

-인접리스트 : O(E)

5. 간선 리스트

-배열을 이용해서 구현

-간선을 모두 저장하고 있다.

-E라는 배열에 간선을 모두 저장 : E[M][2] (M은 간선 개수, 2는 간선의 시작점, 끝점의 정점을 저장)

-각 간선의 앞 정점을 기준으로 개수를 센다

-cnt[i] : i 정점으로 시작하는 간선의 개수 

for(int i=0;i<m;i++){

cnt[E[i][0]]++;

}

for(int i=0;i<=n;i++){

cnt[i]=cnt[i-1]+cnt[i];

}

-i번 정점과 연결된 간선은 E 배열의 cnt[i-1] 부터 cnt[i]-1 까지 이다.

-예를 들어 3번 정점과 연결된 간선은 E[cnt[2]]~E[cnt[3]-1]

6. 대부분의 문제는 인접리스트를 이용해서 풀 수 있음

-특별한 경우 간선리스트나 인접행렬을 사용