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

Ma trận kề của một đồ thị là một 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 phía 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 hàng i và cột j sẽ là 1 (hoặc giá trị khác 0 cho đồ thị có trọng số), ngược lại vị trí đó sẽ giữ 0.

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

• Biểu diễn ma trận kề chiếm O(V²) bộ nhớ khi được tính toán. Khi đồ thị có số cạnh tối đa và số cạnh tối thiểu, trong cả hai trường hợp bộ nhớ yêu cầu đều giống nhau.

Đầu vào

Đầu ra

Thuật toán

add_edge(u, v)

Đầu vào - Các đỉnh u và v của một cạnh {u,v}

Đầu ra - Ma trận kề của đồ thị G

Bắt đầu
    adj_matrix[u, v] := 1
    adj_matrix[v, u] := 1
Kết thúc

Mã ví dụ

#include<iostream> 
using namespace std; 

int vertArr[20][20]; //ma trận kề ban đầu 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) { 
    //hàm thêm cạnh vào ma trận 
    vertArr[u][v] = 1; 
    vertArr[v][u] = 1; 
} 

main(int argc, char* argv[]) { 
    int v = 6; //có 6 đỉnh trong đồ thị 
    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); 
}

Kết quả

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