배열로 인접행렬 vs 벡터로 인접 리스트

 

사실 그래프의 연결 상태를 표현할 때

우리는 배열로 많이 하곤 한다.

하지만 행렬을 이용했을 때 가장 큰 문제점은

노드의 개수의 제곱에 비례하는 메모리를 사용하기 때문이다.

노드의 개수 범위가 만약 100000이라면 십만의 제곱은... 우선 0이 10개다.

10억이다.

int로 저장했다면 10억 * 4byte = 40억 byte 다.

그러면.. 약 3기가 바이트..

그래서 우리는 굳이 연결되지 않은 부분까지 저장하기는 그래서

인접리스트로 저장하기로 했다.

 

그렇게 되면 실제로 연결된 부분만 저장할 수 있다.

즉, vector을 원소로 하는 vector 또는 array를 만들어 해당 인덱스랑 연결된 노드들의 정보를 넣는 것이다.

 

실제로 이는 문제풀이할 때 노드의 수로 초과하는 것을 막아주기 때문에 유용하다고 할 수 있다.