Chương trình C++ triển khai danh sách kề (Adjacency List)

Biểu diễn danh sách kề của một đồ thị là biểu diễn bằng danh sách liên kết. Trong biểu diễn này, chúng ta có một mảng các danh sách. Kích thước mảng là V. Ở đây V là số đỉnh. Nói cách khác, chúng ta có một mảng để lưu trữ V danh sách khác nhau. Nếu một tiêu đề danh sách là đỉnh u, thì nó biểu thị rằng nó sẽ chứa tất cả các đỉnh kề của u.

Độ phức tạp của biểu diễn Danh sách kề

• Biểu diễn này chiếm O(V+2E) cho đồ thị vô hướng, và O(V+E) cho đồ thị có hướng. Nếu số cạnh tăng lên, bộ nhớ yêu cầu cũng sẽ tăng.

Đầ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