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

인접 행렬(Adjacency Matrix)이란?

그래프의 인접 행렬은 V × V 크기의 정방행렬(square matrix)입니다. 여기서 V는 그래프 G가 가진 정점(vertex)의 개수를 의미합니다.

행렬의 행과 열에는 각각 V개의 정점이 배치되며, 만약 정점 i에서 정점 j로 이어지는 간선(edge)이 존재한다면 해당 위치, 즉 i번째 행과 j번째 열에 1을 기록합니다. 가중치 그래프(weighted graph)의 경우에는 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

무방향 그래프라면 간선은 양방향으로 연결되므로 (u, v)와 (v, u) 두 위치 모두에 1을 설정해야 합니다.

C++ 예제 코드

#include<iostream>
using namespace std;
int vertArr[20][20]; // 인접 행렬, 초기값은 모두 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) { // 행렬에 간선을 추가하는 함수
    vertArr[u][v] = 1;
    vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; // 그래프는 6개의 정점을 가짐
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

위 코드에서는 20×20 크기의 2차원 배열을 미리 선언하여 인접 행렬로 사용하며, 초기 상태는 모두 0으로 채워져 있습니다. add_edge() 함수가 호출될 때마다 해당 정점 쌍의 위치에 1이 기록되고, 마지막에 displayMatrix() 함수가 완성된 인접 행렬 전체를 화면에 출력합니다.