C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

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

グラフの接続行列は、メモリに保存するグラフの別の表現です。この行列は正方行列ではありません。接続行列の次数はVxEです。ここで、Vは頂点の数、Eはグラフのエッジの数です。

この行列の各行に頂点を配置し、各列にエッジを配置します。エッジe{u、v}のこの表現では、列eの場所uとvに対して1でマークされます。

隣接行列表現の複雑さ

  • 接続行列表現は、計算中にO（Vx E）のスペースを取ります。完全グラフの場合、エッジの数はV（V-1）/2になります。したがって、接続行列はメモリ内でより大きなスペースを取ります。

入力

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

出力


E0
E1
E2
E3
E4
E5
E6
E7
E8
0
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
2
0
0
1
0
0
1
1
0
0
3
0
1
0
0
0
1
0
1
0
4
1
0
0
1
0
0
0
0
1
5
0
0
0
0
1
0
1
1
1

アルゴリズム

add_edge（u、v）

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

出力 −グラフGの接続行列G

最初は、接続行列のエッジカウントed_cntが0です。

Begin
   ed_cnt := ed_cnt + 1
   inc_matrix[u, ed_cnt] := 1
   inc_matrix[v, ed_cnt] := 1
End

サンプルコード（C ++）

#include<iostream>
using namespace std;
int inc_arr[20][20]; //initial array to hold incidence matrix
int ed_no = 0;
void displayMatrix(int v, int e) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < e; j++) {
         cout << inc_arr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) { //function to add edge into the matrix with edge number
   inc_arr[u][ed_no] = 1;
   inc_arr[v][ed_no] = 1;
   ed_no++; //increase the edge number
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   int e = 9; //there are 9 edges 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, e);
}

出力

1 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 1 0 0 1 1 0 0
0 1 0 0 0 1 0 1 0
1 0 0 1 0 0 0 0 1
0 0 0 0 1 0 1 1 1

  1. 隣接リストを使用してグラフを表現するC++プログラム

    グラフの隣接リスト表現は、リンクリスト表現です。この表現では、リストの配列があります。配列のサイズはVです。ここで、Vは頂点の数です。つまり、V個の異なるリストを格納する配列があると言えます。リストヘッダーが頂点uの場合、uの隣接するすべての頂点を保持することを意味します。 隣接リスト表現の複雑さ この表現は、無向グラフの場合はO（V + 2E）を取り、有向グラフの場合はO（V + E）を取ります。エッジの数を増やすと、必要なスペースも増えます。 入力： 出力： アルゴリズム add_edge（adj_list、u、v） 入力 −エッジ{u、v}のuとv、およ

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

    グラフの隣接行列は、サイズV x Vの正方行列です。Vは、グラフGの頂点の数です。この行列では、各辺にV個の頂点がマークされています。グラフにiからjの頂点までのエッジがある場合、i thの隣接行列に 行とjth 列は1（または加重グラフの場合はゼロ以外の値）になります。それ以外の場合、その場所は0を保持します。 隣接行列表現の複雑さ 隣接行列表現はO（V 2 ）計算中のスペースの量。グラフに最大数のエッジと最小数のエッジがある場合、どちらの場合も必要なスペースは同じになります。 入力 出力 0 1 2 3 4 5