[그래프의 표현] 인접 리스트

인접 리스트

 그래프를 표현하는 방법중의 한가지 방법이다. 즉 링크드 리스트 ( 벡터) 를 사용한 배열로 그래프를 표현해 주는 방법이다.  인접 행렬과 달리 간선의 개수로만 검색하는것이 줄어들기 때문에 검색 속도가 빠르다. 즉 아래의 그래프를 표현해 준다면 다음과 같다.

 어찌보면 인접 행렬이랑 뭐가 다르냐??? 라고 물어볼 수 있는데 그건 탐색의 시간에서 큰 차이를 보인다. 인접행렬의 같은경우는 접점의 개수 x 접점의 개수의 맵을 전부 탐색해야 되지만 인접 리스트는 간선의 개수만 탐색 해도 되기 때문에 차이가 난다. 

왼쪽의 그림이 인접 행렬이고, 오른쪽은 인접 리스트인데 속도 면에서도 횟수의 차이가 명백히 나는 것을 볼 수 있다. 

코드 구현

 인접 리스트를 만드는 코드 구현 같은 경우는 매우 짧고 쉽게 만들 수 있따. 여기서 n은 정점의 개수 m 은 간선의 개수이다. u와 v는 간선의 속성으로 연결된 두 정점을 표현한다.

#include <cstdio>
#include <vector>
using namespace std;
vector<int> a[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].push_back(v); a[v].push_back(u);
    }
}