2.6.3 인접 리스트로 그래프 표현하기

행렬을 이용하여 그래프를 표현할 때의 가장 큰 문제점은 노드 개수의 제곱에 비례하는 메모리를 사용한다는 점입니다. 노드 개수가 증가함에 따라 메모리 사용량은 크게 늘어납니다. 그러므로 메모리를 좀 더 적게 사용하는 방법을 생각해봐야 합니다.

어느 그래프에서나 정해진 수의 노드가 있고, 각 노드에서 연결될 수 있는 노드의 최대 개수는 전체 노드 개수와 같습니다. 행렬을 사용할 경우, 두 노드가 서로 연결되어 있지 않더라도 모든 노드 사이의 에지 정보를 저장해야 합니다. 이러한 방식 대신 각 노드에 직접 연결되어 있는 노드의 ID만 저장하는 방식으로 그래프를 표현할 수 있습니다. 이러한 방식을 인접 리스트(adjacency list)라고 합니다.

다음 연습 문제에서 인접 리스트를 사용하여 그래프를 표현해보고, 앞서 인접 행렬을 사용하는 방식과의 차이점에 대해 생각해보겠습니다.