인접 행렬을 구현하는 C++ 프로그램

그래프의 인접 행렬은 V x V 크기의 정방 행렬입니다. V는 그래프 G의 꼭짓점 수입니다. 이 행렬에서 각 변의 V 꼭짓점은 표시됩니다. 그래프에 i에서 j 정점까지의 모서리가 있는 경우 i ^번째 의 인접 행렬에서 행 및 j ^번째 열은 1(또는 가중치 그래프의 경우 0이 아닌 값)이 됩니다. 그렇지 않으면 해당 위치는 0을 유지합니다.

인접 행렬 표현의 복잡성:

• 인접 행렬 표현은 계산되는 동안 O(V2)의 공간을 차지합니다. 그래프에 최대 모서리 수와 최소 모서리 수가 있을 때 두 경우 모두 필요한 공간은 동일합니다.

입력:

출력:

알고리즘

add_edge(u, v)

입력 :에지의 u와 v {u,v}

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

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

예제 코드

#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