C++ 연결 리스트(인접 리스트)로 그래프 표현하기 – 알고리즘과 구현 코드

그래프 표현 방식과 공간 복잡도

그래프를 컴퓨터 메모리에 저장하는 방법은 여러 가지가 있습니다. 대표적으로 행렬(matrix) 기반 표현과 인접 리스트(adjacency list, 연결 리스트) 기반 표현이 있습니다.

먼저 참고로, 그래프의 인시던스 행렬(incidence matrix)은 정점과 간선의 관계를 나타내는 또 다른 표현 방식입니다. 이 행렬은 정방행렬이 아니며 크기는 V × E입니다(여기서 V는 정점의 수, E는 간선의 수). 행에는 정점을, 열에는 간선을 배치하며, 간선 e = {u, v}가 존재하면 해당 열의 u와 v 위치를 1로 표시합니다.

• 행렬 방식의 공간 복잡도: 인시던스 행렬 표현은 계산 시 O(V × E)의 공간을 차지합니다. 완전 그래프(complete graph)의 경우 간선 수가 V(V−1)/2가 되므로, 행렬 방식은 상당히 많은 메모리를 소모하게 됩니다.

• 반면 인접 리스트는 O(V + E)의 공간만 필요하기 때문에, 간선 수가 적은 희소 그래프(sparse graph)를 표현할 때 훨씬 효율적입니다.

알고리즘: add_edge(adj_list, u, v)

입력: 간선 {u, v}를 이루는 두 정점 u와 v, 그리고 인접 리스트

출력: 그래프 G의 인접 리스트

시작
   인덱스 u 위치의 리스트에 v를 추가한다
   인덱스 v 위치의 리스트에 u를 추가한다
끝

무향 그래프에서는 간선이 양방향으로 연결되므로, 양쪽 정점의 리스트에 서로의 정점을 모두 추가해 주어야 합니다.

C++ 예제 코드

아래 코드는 C++ STL의 std::list를 사용하여 정점 6개짜리 무향 그래프를 인접 리스트로 표현합니다. 간선을 추가한 뒤 전체 인접 리스트를 출력합니다.

#include<iostream>
#include<list>
#include<iterator>
using namespace std;

void displayAdjList(list<int> adj_list[], int v) {
    for(int i = 0; i<v; i++) {
        cout << i << "--->";
        list<int> :: iterator it;
        for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
            cout << *it << " ";
        }
        cout << endl;
    }
}

void add_edge(list<int> adj_list[], int u, int v) { // u번째 리스트에 v를, v번째 리스트에 u를 추가
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
}

int main(int argc, char* argv[]) {
    int v = 6; // 그래프에는 6개의 정점이 존재
    // 크기가 6인 리스트 배열 생성
    list<int> adj_list[v];
    add_edge(adj_list, 0, 4);
    add_edge(adj_list, 0, 3);
    add_edge(adj_list, 1, 2);
    add_edge(adj_list, 1, 4);
    add_edge(adj_list, 1, 5);
    add_edge(adj_list, 2, 3);
    add_edge(adj_list, 2, 5);
    add_edge(adj_list, 5, 3);
    add_edge(adj_list, 5, 4);
    displayAdjList(adj_list, v);
    return 0;
}

실행 결과

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4

각 줄은 해당 정점에 연결된 정점들을 의미합니다. 예를 들어 첫 번째 줄 "0--->4 3"은 정점 0이 정점 4와 정점 3에 연결되어 있음을 보여줍니다. 이처럼 인접 리스트를 사용하면 각 정점의 이웃 정보를 동적 배열 없이도 간단하고 효율적으로 저장할 수 있습니다.