C++로 그래프를 인시던스 행렬(Incidence Matrix)로 표현하는 방법

인시던스 행렬(Incidence Matrix)이란?

그래프를 메모리에 저장하는 방법 중 하나가 바로 인시던스 행렬입니다. 인접 행렬과 달리 인시던스 행렬은 정사각형 행렬이 아니며, 그 크기는 V × E입니다. 여기서 V는 그래프의 정점(vertex) 수, E는 간선(edge) 수를 의미합니다.

행렬의 각 행(row)에는 정점이 배치되고, 각 열(column)에는 간선이 배치됩니다. 간선 e = {u, v}가 존재하는 경우, 해당 간선의 열에서 u번째 행과 v번째 행의 값이 1로 표시됩니다.

공간 복잡도

인시던스 행렬 표현은 O(V × E)만큼의 공간을 필요로 합니다. 특히 완전 그래프(complete graph)의 경우 간선 수가 V(V−1)/2에 달하기 때문에, 인접 행렬(O(V²))보다 훨씬 많은 메모리를 차지할 수 있습니다.

알고리즘

add_edge(u, v)

입력: 간선 {u, v}를 구성하는 두 정점 u와 v

출력: 그래프 G의 인시던스 행렬

간선 번호 ed_cnt는 처음에 0으로 초기화되며, 간선이 추가될 때마다 1씩 증가합니다.

Begin
   ed_cnt := ed_cnt + 1
   inc_matrix[u, ed_cnt] := 1
   inc_matrix[v, ed_cnt] := 1
End

즉, 새로운 간선이 추가될 때마다 새로운 열을 만들고, 그 열에서 두 정점에 해당하는 행의 값을 1로 설정하는 방식입니다.

C++ 예제 코드

아래 예제는 정점 6개(0~5)와 간선 9개로 구성된 무방향 그래프를 인시던스 행렬로 변환합니다.

#include <iostream>
using namespace std;

int inc_arr[20][20]; // 인시던스 행렬을 저장할 배열
int ed_no = 0;       // 현재까지 추가된 간선의 개수

void displayMatrix(int v, int e) {
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < e; j++) {
            cout << inc_arr[i][j] << " ";
        }
        cout << endl;
    }
}

void add_edge(int u, int v) { // 간선을 행렬에 추가하는 함수
    inc_arr[u][ed_no] = 1;
    inc_arr[v][ed_no] = 1;
    ed_no++; // 간선 번호 증가
}

int main() {
    int v = 6; // 정점 6개
    int e = 9; // 간선 9개

    add_edge(0, 4);
    add_edge(0, 3);
    add_edge(1, 2);
    add_edge(1, 4);
    add_edge(1, 5);
    add_edge(2, 3);
    add_edge(2, 5);
    add_edge(5, 3);
    add_edge(5, 4);

    displayMatrix(v, e);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 인시던스 행렬이 출력됩니다. 각 행은 정점을, 각 열은 간선(E0~E8)을 나타냅니다.

예를 들어 간선 E0은 정점 0과 4를 연결하므로, 0행과 4행의 E0 열 값이 1로 표시된 것을 확인할 수 있습니다.

마무리

인시던스 행렬은 간선 중심의 정보를 직관적으로 보여준다는 장점이 있지만, 간선이 많은 그래프에서는 메모리 낭비가 커질 수 있습니다. 따라서 간선 단위의 정보를 직접 다루어야 하는 특수한 경우가 아니라면, 일반적으로는 인접 리스트나 인접 행렬이 더 효율적인 선택입니다.