โปรแกรม C++ สร้างกราฟสุ่มด้วยวิธี Random Edge Selection

การสร้างกราฟสุ่มด้วยการเลือกเส้นขอบแบบสุ่ม

ในโปรแกรมนี้จะสร้างกราฟสุ่มสำหรับจุดยอดและเส้นขอบสุ่ม ความซับซ้อนด้านเวลาคือ O(v*e) โดย v คือจำนวนจุดยอด e คือจำนวนเส้นขอบ

อัลกอริทึม

Begin
    พัฒนาฟังก์ชัน GenRandomGraphs() รับ 'e' (จำนวนเส้นขอบ) และ 'v' (จำนวนจุดยอด)
    กำหนดค่าสุ่มให้จำนวนจุดยอดและเส้นขอบของกราฟ ใช้ฟังก์ชัน rand()
    แสดงการเชื่อมต่อของแต่ละจุดยอด ไม่สนใจทิศทาง
    แสดง "Isolated vertex" สำหรับจุดยอดที่ไม่มี degree
End

ตัวอย่างโค้ด

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

void GenRandomGraphs(int NOEdge, int NOVertex) {
    int i, j, edge[NOEdge][2], count;
    i = 0;
    while(i < NOEdge) {
        edge[i][0] = rand()%NOVertex+1;
        edge[i][1] = rand()%NOVertex+1;
        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 << "\nThe generated random graph is: ";
    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!";
        }
        cout << " }";
    }
}

int main() {
    int i, e, n;
    cout << "Random graph generation: ";
    n = 7 + rand()%6;
    cout << "\nThe graph has " << n << " vertices";
    e = rand()%((n*(n-1))/2);
    cout << "\nand has " << e << " edges.";
    GenRandomGraphs(e, n);
}

ผลลัพธ์

Random graph generation:
The graph has 8 vertices and has 18 edges.
The generated random graph is:
    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 }