Chương trình C++ biểu diễn đồ thị bằng ma trận nhập (Incidence Matrix)

Ma trận nhập (incidence matrix) của một đồ thị là một biểu diễn khác của đồ thị để lưu trữ vào bộ nhớ. Ma trận này không phải là ma trận vuông. Cấp của ma trận nhập 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 đặ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 tại 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 nhập chiếm O(V x E) bộ nhớ khi đượ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 nhập chiếm bộ nhớ lớn hơn.

Đầ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 nhập của đồ thị G

Ban đầu, có biến đếm cạnh ed_cnt = 0 cho ma trận nhập.

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

Mã ví dụ (C++)

#include<iostream> 
using namespace std; 

int inc_arr[20][20]; //mảng ban đầu chứa ma trận nhập 
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) { 
    //hàm thêm cạnh vào ma trận với số cạnh 
    inc_arr[u][ed_no] = 1; 
    inc_arr[v][ed_no] = 1; 
    ed_no++; //tăng số cạnh 
} 

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

Kết quả

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