2D 배열을 사용하여 그래프를 표현하는 C++ 프로그램

2차원 배열을 이용하여 그래프를 표현한 C++ 프로그램입니다.

이 알고리즘의 시간 복잡도는 O(v*v)입니다.

알고리즘

Begin
   Take the input of the number of vertex ‘v’ and edges ‘e’.
   Assign memory to the graph[][] matrix.
   Take the input of ‘e’ pairs of vertexes of the given graph in graph[][].
   For each pair of connected vertex(v1, v2), store 1 in the graph[][] at the index (v1, v2) and (v2, v1).
   Print the matrix using PrintMatrix().
End

예시 코드

#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);
}

출력

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