도시가 다섯 개 있고, 도시 사이에는 도로가 있는 경우도 있고 없는 경우도 있다고 하겠습니다. 이때 이 관계를 그래프로 어떻게 표현해야 할까요? 먼저 도시를 0부터 시작해서 4까지 숫자를 매깁니다. 도시와 도시 사이에 도로가 있다면 이 두 정점 사이에 에지가 있는 것입니다. 여기까지 모델링을 했으면 이제 이를 코드로 표현해야겠지요.

그래프를 표현하는 두 가지 방법에 인접 리스트(adjacency list)와 인접 행렬(adjacency matrix)이 있습니다. 하나씩 자세히 살펴보겠습니다.

그림 6-12는 그래프를 인접 리스트로 표현한 것입니다.

▲ 그림 6-12 인접 리스트