[C++알고리즘][정점들을 인접행렬, 인접 리스트로 표현하기]

• 인접 행렬

위와 같이 무방향으로 노드들이 이어져 있다. 이제 이 그래프를 저장하는 2차원배열 ary[6][6]를 만들어준다.

그리고 노드a과 노드b가 이어져있다는 것을 배열로 표현해준다면 ary[a][b] = true, ary[b][a] = true 로 표현해줄 수 있다. 하지만 여기서 단방향 그래프로 만들고 싶으면 예를 들어 a->b인 노드이면 ary[a][b] = true 라고만 해주면 된다.

이렇게 표현하게 된다면 위의 그림은 ary[6][6]의 크기의 배열이 필요하다(ex. ary[5][4] = 1)

이걸 배열로 나타낸다면 아래와 같다.

[0]	[1]	[2]	[3]	[4]	[5]
[1]	0	1	0	0	0
[2]	1	0	1	0	0
[3]	0	1	0	0	1
[4]	0	0	0	0	1
[5]	0	0	1	1	0

하지만 이렇게 하게 된다면 쓰는 메모리 공간보다 안 쓰는 공간의 더 커지는 경우가 많다. 메모리 공간을 최소화 하여 저장하는 방법이 벡터를 이용한 인접리스트이다.

 

• 인접리스트

구조를 먼저 보여주자면 v[a].push_back(b) 이런 구조이다. (a,b는 노드) 

양방향 그래프이면 v[a].push_back(b) v[b].push_back(a) a,b를 바꾸어서 한번씩 해주면된다.

단방향 그래프이면 (ex. a->b인 그래프) v[a].push_back(b)로 해주면된다.

 

이런식으로 짜면 필요할 때마다 벡터를 늘려 가며 사용하므로 불필요한 메모리의 사용을 줄일 수 있다.

그리고 인접리스트는 또 하나의 장점이 있다. 바로 가중치를 그래프일때 간편하다는 이유이다.

 

만약 a->b로 가는 그래프에서 가중치 10이 있다면 

v[a].push_back(make_pair(b,w)) (a,b는 노드 w는 가중치) 이런식으로 매우 간편하게 데이터를 저장할 수 있다.

 

 

코드

#include <iostream>
#include <vector>
#define max 6
using namespace std;
int main(void){
    //인접 행렬 생성
    int ary[max][max];
    for(int i = 0;i<max;i++){
        int a,b;
        cin >> a >> b;
        ary[a][b] = 1;
        ary[b][a]
    }
    
    // 인접 리스트 생성
    vector<int> adj[max];
    for(int i = 0;i<max;i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}