2.6.1 인접 행렬로 그래프 표현하기

간단하게 그래프를 표현하는 방법에 대해 알아보겠습니다. 노드의 집합이 있고, 노드끼리 서로 연결될 수 있다고 가정하겠습니다. 노드가 N개 있을 경우, 이 그래프는 N×N 크기의 2차원 배열로 표현할 수 있습니다. 이 배열에서 특정 원소는 해당 원소 인덱스에 해당하는 노드 사이의 가중치를 표현합니다. 즉, data[1][2]는 1번 노드와 2번 노드를 잇는 에지의 가중치를 나타냅니다. 이러한 방식으로 그래프를 표현하는 방법을 인접 행렬(adjacency matrix)이라고 합니다. 두 노드 사이에 에지가 존재하지 않으면 해당 원소에 -1을 설정합니다.

그림 2-18은 전 세계 주요 도시를 연결하는 항공 네트워크를 표현한 가중 그래프의 예입니다. 에지에 표현된 숫자는 두 도시 간의 가상의 거리를 나타냅니다.

▲ 그림 2-18 도시 간의 항공 네트워크

그림 2-18에서 런던에서 두바이로 가기 위해 직접 갈 수도 있고, 서울을 거쳐서 갈 수도 있습니다. 즉, 특정 도시에서 다른 도시로 이동하기 위한 다양한 경로가 존재합니다. 또한 특정 도시에서 다른 여러 도시를 거쳐, 중복되지 않은 에지를 통해 다시 출발 도시로 돌아올 수도 있습니다. 이러한 특징은 트리에서는 볼 수 없는 속성입니다.

그럼 인접 행렬을 이용하여 그림 2-18의 그래프를 표현해보겠습니다.