C++로 구현하는 그래프 인접 행렬(Adjacency Matrix)

그래프의 인접 행렬이란?

그래프의 인접 행렬(Adjacency Matrix)은 V × V 크기의 정방행렬로, 여기서 V는 그래프 G의 정점(vertex) 개수를 의미합니다. 이 행렬에서는 행과 열 양쪽 축에 V개의 정점이 배치됩니다. 만약 그래프에 정점 i에서 정점 j로 향하는 간선이 존재한다면, 인접 행렬의 i번째 행과 j번째 열 위치에 1이 기록됩니다(가중치 그래프라면 해당 가중치 값처럼 0이 아닌 값이 저장됨). 반대로 간선이 존재하지 않으면 그 자리에는 0이 들어갑니다.

인접 행렬 표현의 복잡도

• 인접 행렬 표현은 생성 시 O(V²)의 공간을 필요로 합니다. 그래프가 최대한 많은 간선을 가지든 최소한의 간선만 가지든, 필요한 공간의 크기는 항상 동일합니다.

입력 및 출력 예시

입력:

출력:

알고리즘

add_edge(u, v)

입력: 간선 {u, v}를 이루는 두 정점 u와 v

출력: 그래프 G의 인접 행렬

Begin
   adj_matrix[u, v] := 1
   adj_matrix[v, u] := 1
End

C++ 예제 코드

아래 코드는 20×20 크기의 2차원 배열 vertArr를 인접 행렬로 사용하며, 초기값은 모두 0입니다. 무향 그래프이므로 add_edge() 함수는 대칭 위치인 [u][v]와 [v][u] 모두에 1을 설정하고, displayMatrix() 함수는 완성된 인접 행렬을 화면에 출력합니다.

#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
    int i, j;
    for(i = 0; i < v; i++) {
        for(j = 0; j < v; j++) {
            cout << vertArr[i][j] << " ";
        }
        cout << endl;
    }
}
void add_edge(int u, int v) {       //function to add edge into the matrix
    vertArr[u][v] = 1;
    vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
   int v = 6;    //there are 6 vertices in the graph
   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);
}

실행 결과

0 0 0 1 1 0
0 0 1 0 1 1
0 1 0 1 0 1
1 0 1 0 0 1
1 1 0 0 0 1
0 1 1 1 1 0