Chương trình C++ triển khai ma trận kề (Adjacency Matrix)

Ma trận kề của một đồ thị là một ma trận vuông kích thước V x V. Trong đó V là số đỉnh của đồ thị G. Trong ma trận này, mỗi phía có 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 một giá trị khác 0 cho đồ thị có trọng số), ngược lại vị trí đó sẽ giữ giá trị 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 bằng 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