C++에서는 2차원 배열을 이용해 그래프(graph)를 아주 간단하게 표현할 수 있습니다. 이번 글에서는 정점(vertex)과 간선(edge) 정보를 입력받아 인접 행렬(adjacency matrix) 형태로 그래프를 생성하고 출력하는 프로그램을 단계별로 살펴보겠습니다.
이 알고리즘의 시간 복잡도는 O(V²)입니다. 정점이 V개일 때 V×V 크기의 행렬 전체를 확인해야 하기 때문입니다.
알고리즘
- 그래프의 정점 개수 'v'와 간선 개수 'e'를 입력받습니다.
- graph[][] 행렬에 동적으로 메모리를 할당하고, 모든 요소를 0으로 초기화합니다.
- 간선의 개수(e)만큼 서로 연결된 정점 쌍(v1, v2)을 입력받습니다.
- 연결된 각 정점 쌍에 대해 graph[v1][v2]와 graph[v2][v1] 위치에 1을 저장합니다. 무방향 그래프이므로 양쪽 모두 표시하는 것입니다.
- PrintMatrix() 함수를 호출하여 완성된 인접 행렬을 화면에 출력합니다.
예제 코드
#include<iostream>
#include<iomanip>
using namespace std;
void PrintMatrix(int **matrix, int n) {
int i, j;
cout<<"\n\n"<<setw(4)<<"";
for(i = 0; i < n; i++)
cout<<setw(3)<<"("<<i+1<<")";
cout<<"\n\n";
for(i = 0; i < n; i++) {
cout<<setw(3)<<"("<<i+1<<")";
for(j = 0; j < n; j++) {
cout<<setw(4)<<matrix[i][j];
}
cout<<"\n\n";
}
}
int main() {
int i, v, e, j, v1, v2;
cout<<"Enter the number of vertexes of the graph: ";
cin>>v;
int **graph;
graph = new int*[v];
for(i = 0; i < v; i++) {
graph[i] = new int[v];
for(j = 0; j < v; j++) graph[i][j] = 0;
}
cout<<"\nEnter the number of edges of the graph: ";
cin>>e;
for(i = 0; i < e; i++) {
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nV(1): ";
cin>>v1;
cout<<"V(2): ";
cin>>v2;
graph[v1-1][v2-1] = 1;
graph[v2-1][v1-1] = 1;
}
PrintMatrix(graph, v);
}코드 핵심 포인트
- 동적 메모리 할당: new 연산자를 사용해 실행 시점에 정점 개수에 맞는 2차원 배열을 생성합니다.
- 0 초기화: 간선이 없는 정점 쌍은 기본값 0으로 유지되어 연결 여부를 직관적으로 판단할 수 있습니다.
- 양방향 저장: 무방향 그래프이므로 (v1, v2)와 (v2, v1) 두 위치에 모두 1을 저장합니다.
- 행렬 출력: iomanip 헤더의 setw()를 활용해 열을 정렬하여 가독성 좋게 출력합니다.
실행 결과
Enter the number of vertexes of the graph: 5 Enter the number of edges of the graph: 4 Enter the vertex pair for edge 1 V(1): 2 V(2): 1 Enter the vertex pair for edge 2 V(1): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 1 V(2): 1 Enter the vertex pair for edge 4 V(1): 3 V(2): 1 (1) (2) (3) (4) (5) (1) 1 1 1 0 0 (2) 1 0 1 0 0 (3) 1 1 0 0 0 (4) 0 0 0 0 0 (5) 0 0 0 0 0
정리
2차원 배열 기반의 인접 행렬은 구현이 간단하고 두 정점의 연결 여부를 O(1) 시간에 바로 확인할 수 있다는 장점이 있습니다. 다만 정점 수가 많고 간선이 적은 희소 그래프(sparse graph)에서는 메모리가 낭비될 수 있으므로, 그래프의 특성에 따라 인접 리스트 방식과 비교하여 선택하는 것이 좋습니다.