Chương trình C ++ để biểu diễn đồ thị bằng ma trận kề

Ma trận kề của đồ thị là ma trận vuông kích thước V x V. V là số đỉnh của đồ thị G. Trong ma trận này, mỗi cạnh V đỉnh được đánh dấu. Nếu đồ thị có một số cạnh từ đỉnh i đến đỉnh j, thì trong ma trận kề tại i ^th hàng và thứ j cột nó sẽ là 1 (hoặc một số giá trị khác 0 cho biểu đồ có trọng số), nếu không thì vị trí đó sẽ chứa 0.

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

• Biểu diễn ma trận kề nhận O (V ² ) lượng không gian trong khi nó được tính toán. Khi biểu đồ có số cạnh tối đa và số cạnh nhỏ nhất, trong cả hai trường hợp, không gian bắt buộc sẽ bằng nhau.

Đầ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 kề của đồ thị G

Begin
adj_matrix[u, v] := 1
adj_matrix[v, u] := 1
End

Mã mẫu

#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);
}

Đầu ra

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