Chương trình C++ biểu diễn đồ thị bằng danh sách liên kết

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(adj_list, u, v)

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

Đầu ra - Danh sách kề của đồ thị G

Bắt đầu
    Thêm v vào danh sách tại chỉ số u
    Thêm u vào danh sách tại chỉ số v
Kết thúc

Mã ví dụ

#include<iostream> 
#include<list> 
#include<iterator> 
using namespace std; 

void displayAdjList(list<int> adj_list[], int v) { 
    for(int i = 0; i < v; i++) { 
        cout << i << "--->"; 
        list<int> :: iterator it; 
        for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) { 
            cout << *it << " "; 
        } 
        cout << endl; 
    } 
} 

void add_edge(list<int> adj_list[], int u, int v) { 
    //thêm v vào danh sách u, và u vào danh sách v 
    adj_list[u].push_back(v); 
    adj_list[v].push_back(u); 
} 

main(int argc, char* argv[]) { 
    int v = 6; //có 6 đỉnh trong đồ thị 
    //tạo một mảng các danh sách có kích thước 6 
    list<int> adj_list[v]; 
    add_edge(adj_list, 0, 4); 
    add_edge(adj_list, 0, 3); 
    add_edge(adj_list, 1, 2); 
    add_edge(adj_list, 1, 4); 
    add_edge(adj_list, 1, 5); 
    add_edge(adj_list, 2, 3); 
    add_edge(adj_list, 2, 5); 
    add_edge(adj_list, 5, 3); 
    add_edge(adj_list, 5, 4); 
    displayAdjList(adj_list, v); 
}

Kết quả

0--->4 3 1--->2 4 5 2--->1 3 5 3--->0 2 5 4--->0 1 5 5--->1 2 3 4