그래프 저장방법 - 인접행렬, 인접리스트, 간선리스트

그래프를 저장하는 방법에는 3가지 방법이 있다.

바로 인접행렬, 인접리스트, 간선리스트이다.

순서대로 각각 비교해 보도록 하겠다.

i) 인접 행렬

V*V 의 2차원 행렬을 만들어 처리하는 방법이다.

A[i][j] 에 대해 설명하면 i 에서 j로 가는 간선이 있으면 w(가중치) 의 값을 대입하고 없으면 0 을 대입한다.

그래프에서 가중치가 따로 나와있지 않는다면 1로 가정하고 처리하면 된다.

양방향 그래프라면 A[i][j]와 A[j][i]의 값이 같은값을 넣어야한다. 따라서 공간을 많이, 중복된 값을 차지한다는 점에서 자주 사용하는 방법은 아니다.

코트를 통해 간단하게 나타내면 아래와 같다.

#include <iostream>

#include <vector>

int a[10][10];

int main(){

    int n, m;

    scanf("%d %d", &n,&m);

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

        int u,v;

        scanf("%d %d", &u,&v);

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

    }

    

    return 0;

}

ii) 인접 리스트

링크드리스트를 사용해 그래프는 저장하는 방법이다. 

A[i]에 대해 설명하면 i와 연결된 정점에 대해 저장하는 것이다. 또한 링크드리스트는 매우 복잡하지만 현재 C++에서 vector를 지원하기에 vector를 이용해 구현을 한다.

또한 공간을 적게 차지해 현재 그래프를 저장하는 방법중 가장 많이 사용하는 방법이다.

#include <iostream>

#include <vector>

using namespace std;

vector<int> a[10];

int main() {

    int m,n;

    scanf("%d %d", &n,&m);

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

        int u,v;

        scanf("%d %d", &u,&v);

        a[u].push_back(v);

    }

}

※ 벡터를 사용할 때 주의해야 할 점

vector<int> a(10)  과 vector<int> a[10] 은 다르다는 것이다. 

vector<int> a(10) 은 1차원 벡터를 의미하고  vector<int> a[10] 은 2차원 백터를 의미한다. 즉  a백터가 10개를 가지고 있다 라는 것이다. 

따라서 헷갈리지 않게 작성하고 싶다면  1차원 벡터는 그대로 vector<int> a(10)  으로 작성하고

                                                          2차원 벡터는vector<vector<int> >a(10)  으로 작성하는것이 좋다.

iii) 간선 리스트

간선리스트에 대해서는 따로 설명하지 않겠다. 그 이유는 세가지 방법중 가장 잘 안쓰는 방법이기 때문이다. 이 간선 리스트를 사용할 때에는 아마 STL을 이용하지 못하는 상황에서만 사용한다.