隣接行列を使用してグラフを表現するC++プログラム

グラフの隣接行列は、サイズV x Vの正方行列です。Vは、グラフGの頂点の数です。この行列では、各辺にV個の頂点がマークされています。グラフにiからjの頂点までのエッジがある場合、i ^th の隣接行列に 行とj ^th 列は1（または加重グラフの場合はゼロ以外の値）になります。それ以外の場合、その場所は0を保持します。

隣接行列表現の複雑さ

• 隣接行列表現はO（V ² ）計算中のスペースの量。グラフに最大数のエッジと最小数のエッジがある場合、どちらの場合も必要なスペースは同じになります。

入力

出力

アルゴリズム

add_edge（u、v）

入力 −エッジのuとv {u、v}

出力 −グラフGの隣接行列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