그래프는 현실 세계의 다양한 상호 관계를 시각화하는 데 사용되는 자료 구조입니다. 그래프를 표현하는 방법에는 여러 가지가 있습니다. 이번 글에서는 대표적인 그래프 표현 방법인 ‘인접 리스트’와 ‘인접 행렬’에 대해 알아보겠습니다.

1. 인접 리스트 (Adjacency List)

인접 리스트는 그래프의 각 정점마다 인접한 정점들을 리스트로 나타내는 방식입니다. 각 정점을 인덱스로 가지는 리스트를 만들고, 해당 정점과 연결된 정점들을 리스트로 저장합니다.

예를 들어, 다음과 같은 그래프가 있다고 가정해봅시다.

1 -- 2
|    |
3 -- 4

이 그래프를 인접 리스트로 표현하면 다음과 같습니다.

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}

각 키(Key)는 정점을 의미하고, 해당 값(Value)은 인접한 정점들의 리스트입니다.

2. 인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프의 각 정점들을 행과 열로 표현한 2차원 배열입니다. 행과 열의 인덱스는 정점을 나타내며, 배열의 값은 해당 정점들 간의 연결 여부를 나타냅니다.

예를 들어, 위의 그래프를 인접 행렬로 표현하면 다음과 같습니다.

graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]

행렬의 (i, j) 위치의 값이 1이라면 정점 i와 j가 연결되어 있음을 의미하고, 0이라면 연결되어 있지 않음을 의미합니다.

결론

인접 리스트와 인접 행렬은 각각 그래프를 표현하는 방법으로 장단점을 가지고 있습니다. 인접 리스트는 메모리를 효율적으로 사용하면서도 연결된 정점들을 빠르게 탐색할 수 있는 반면, 인접 행렬은 메모리를 많이 사용하지만 두 정점의 연결 여부를 빠르게 확인할 수 있습니다.

따라서 그래프의 특성에 따라 적절한 방식을 선택하여 사용해야 합니다.

참고 문헌:

• GeeksforGeeks - Graph Representation
• Wikipedia - Graph (abstract data type)