使用关联矩阵表示图的 C++ 程序

图的关联矩阵是将图存储到内存中的另一种表示方法。这个矩阵不是方阵。关联矩阵的阶数为 V x E。其中 V 是图中顶点的数量，E 是图中边的数量。

在这个矩阵的每一行中，我们放置顶点，在每一列中，放置边。在这种表示方法中，对于一条边 e {u, v}，它将在边 e 的列的 u 和 v 的位置上标记为 1。

邻接矩阵表示法的复杂度

  • 关联矩阵表示法在计算时需要 O(Vx E) 的空间。对于完全图，边的数量将为 V(V-1)/2。因此，关联矩阵在内存中占用更大的空间。

输入

输出


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 的关联矩阵

首先，关联矩阵的边计数 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

更新于: 2019-07-30

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告