각 노드에 인접한 노드를 리스트로 저장하기 때문에 인접 리스트라고 합니다. 이 방법은 앞서 설명한 인접 행렬 방법과 마찬가지로 데이터 저장을 위해 벡터의 벡터를 사용합니다. 다만 안쪽 벡터의 크기가 전체 노드 개수가 아니라 해당 노드에 연결된 노드 개수와 같습니다. addEdge() 함수 구현을 보면 에지 끝에 있는 두 노드에 대해 각각 에지 연결을 설정하는 것을 확인할 수 있습니다. 인접 리스트에 의한 그래프 표현은 전체 에지 개수 E에 비례한 크기의 메모리를 사용합니다.

지금까지 그래프를 구성하는 방법 위주로 알아봤습니다. 그래프를 사용하여 어떤 연산을 수행하려면 그래프를 탐색하는 방법도 알아야 합니다. 그래프 탐색은 크게 너비 우선 탐색(BFS, Breadth-First Search)과 깊이 우선 탐색(DFS, Depth-First Search) 방법으로 나뉩니다. 이 두 방법에 대해서는 ‘6장 그래프 알고리즘 1’에서 자세히 다루겠습니다.