Chương trình C++ biểu diễn đồ thị bằng danh sách kề (Incidence List)

Chương trình này biểu diễn đồ thị bằng danh sách kề (incidence list) và độ phức tạp thời gian của thuật toán là O(e).

Thuật toán

Bắt đầu
    Nhập số đỉnh 'v' và số cạnh 'e', cũng như nhập 'e' cặp đỉnh của đồ thị cho trước vào e[][].
    Với mỗi cạnh, in ra các đỉnh tương ứng liên quan đến kết nối đó.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

int main() {
    int i, v, e, j;
    cout << "Nhập số đỉnh của đồ thị: ";
    cin >> v;
    cout << "\nNhập số cạnh của đồ thị: ";
    cin >> e;
    int edge[e][2];
    for(i = 0; i < e; i++) {
        cout << "\nNhập cặp đỉnh cho cạnh " << i+1;
        cout << "\nV(1): ";
        cin >> edge[i][0];
        cout << "V(2): ";
        cin >> edge[i][1];
    }
    cout << "\n\nBiểu diễn danh sách kề cho đồ thị cho trước: ";
    for(i = 0; i < e; i++) {
        cout << "\n\tE(" << i+1 << ") -> { ";
        cout << "V(" << edge[i][0] << ") , " << "V(" << edge[i][1] << ")";
        cout << " }";
    }
}

Kết quả đầu ra

Nhập số đỉnh của đồ thị: 3
Nhập số cạnh của đồ thị: 4
Nhập cặp đỉnh cho cạnh 1
V(1): 2
V(2): 1
Nhập cặp đỉnh cho cạnh 2
V(1): 1
V(2): 2
Nhập cặp đỉnh cho cạnh 3
V(1): 3
V(2): 2
Nhập cặp đỉnh cho cạnh 4
V(1): 2
V(2): 3

Biểu diễn danh sách kề cho đồ thị cho trước:
E(1) -> { V(2) , V(1) }
E(2) -> { V(1) , V(2) }
E(3) -> { V(3) , V(2) }
E(4) -> { V(2) , V(3) }