使用關聯矩陣表示圖的 C++ 程式

圖的關聯矩陣是將圖儲存到記憶體中的另一種表示方法。這個矩陣不是方陣。關聯矩陣的階數為 V x E。其中 V 是圖中頂點的數量，E 是圖中邊的數量。

在這個矩陣的每一行中，我們放置頂點，在每一列中，放置邊。在這種表示方法中，對於一條邊 e {u, v}，它將在邊 e 的列的 u 和 v 的位置上標記為 1。

鄰接矩陣表示法的複雜度

• 關聯矩陣表示法在計算時需要 O(Vx E) 的空間。對於完全圖，邊的數量將為 V(V-1)/2。因此，關聯矩陣在記憶體中佔用更大的空間。

輸入

輸出

演算法

add_edge(u, v)

輸入 - 邊 {u,v} 的 u 和 v

輸出 - 圖 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

Jennifer Nicholas

更新於: 2019-07-30

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習