Chương trình C ++ để biểu diễn đồ thị bằng ma trận tỷ lệ

Ma trận tỷ lệ của đồ thị là một biểu diễn khác của đồ thị để lưu vào bộ nhớ. Ma trận này không phải là ma trận vuông. Bậc của ma trận tỷ lệ là V x E. Trong đó V là số đỉnh và E là số cạnh trong đồ thị.

Trong mỗi hàng của ma trận này, chúng ta đang đặt các đỉnh, và trong mỗi cột, các cạnh được đặt. Trong biểu diễn này cho một cạnh e {u, v}, nó sẽ được đánh dấu bằng 1 cho vị trí u và v của cột e.

Độ phức tạp của biểu diễn Ma trận kề

• Biểu diễn ma trận tỷ lệ chiếm O (Vx E) lượng không gian trong khi nó được tính toán. Đối với đồ thị hoàn chỉnh, số cạnh sẽ là V (V-1) / 2. Vì vậy, ma trận tỷ lệ chiếm không gian lớn hơn trong bộ nhớ.

Đầu vào

Đầu ra

Thuật toán

add_edge (u, v)

Đầu vào - Chữ u và v của cạnh {u, v}

Đầu ra - Ma trận tỷ lệ của biểu đồ G

Lúc đầu, có số lượng cạnh ed_cnt là 0 cho ma trận tỷ lệ.

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

Mã mẫu (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);
}

Đầu ra

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