Chương trình C++ tạo đồ thị ngẫu nhiên bằng sinh cạnh ngẫu nhiên

Trong chương trình này, một đồ thị ngẫu nhiên được sinh ra cho các đỉnh và cạnh ngẫu nhiên. Độ phức tạp thời gian là O(v * e), với v là số đỉnh, e là số cạnh.

Thuật toán

Bắt đầu
  Phát triển hàm GenRandomGraphs(), với 'e' là số cạnh và 'v' là số đỉnh.
    Gán giá trị ngẫu nhiên cho số đỉnh và cạnh của đồ thị,
    sử dụng hàm rand().
    In kết nối của mỗi đỉnh, không quan tâm hướng.
    In "Đỉnh cô lập" (Isolated vertex) cho đỉnh không có bậc.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
#include <stdlib.h>
using namespace std;

void GenRandomGraphs(int NOEdge, int NOVertex) {
    int i, j, edge[NOEdge][2], count;
    i = 0;
    // Gán giá trị ngẫu nhiên cho đỉnh và cạnh
    while (i < NOEdge) {
        edge[i][0] = rand() % NOVertex + 1;
        edge[i][1] = rand() % NOVertex + 1;
        // In kết nối của mỗi đỉnh
        if (edge[i][0] == edge[i][1])
            continue;
        else {
            for (j = 0; j < i; j++) {
                if ((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) ||
                    (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))
                    i--;
            }
        }
        i++;
    }
    cout << "\nĐồ thị ngẫu nhiên sinh ra: ";
    for (i = 0; i < NOVertex; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for (j = 0; j < NOEdge; j++) {
            if (edge[j][0] == i+1) {
                cout << edge[j][1] << " ";
                count++;
            } else if (edge[j][1] == i+1) {
                cout << edge[j][0] << " ";
                count++;
            } else if (j == NOEdge-1 && count == 0)
                cout << "Isolated Vertex!"; // In "Đỉnh cô lập" cho đỉnh bậc 0
        }
        cout << " }";
    }
}

int main() {
    int i, e, n;
    cout << "Sinh đồ thị ngẫu nhiên: ";
    n = 7 + rand() % 6;
    cout << "\nĐồ thị có " << n << " đỉnh";
    e = rand() % ((n * (n-1)) / 2);
    cout << "\nvà có " << e << " cạnh.";
    GenRandomGraphs(e, n);
}

Kết quả

Sinh đồ thị ngẫu nhiên:
Đồ thị có 8 đỉnh và có 18 cạnh.
Đồ thị ngẫu nhiên sinh ra:
1-> { 5 4 2 }
2-> { 4 8 6 3 1 5 }
3-> { 5 4 7 2 }
4-> { 2 3 7 1 8 5 }
5-> { 3 1 7 4 2 8 }
6-> { 2 8 7 }
7-> { 4 3 5 6 }
8-> { 2 6 4 5 }