โปรแกรม C++ สร้างกราฟ Undirected แบบสุ่มสำหรับจำนวน Edge ที่กำหนด

โปรแกรม C++ สร้างกราฟ undirected แบบสุ่มสำหรับจำนวน edge 'e' ที่กำหนด อัลกอริทึมนี้ใช้กับเครือข่ายขนาดใหญ่ และมี time complexity O(log n)

อัลกอริทึม

เริ่มต้น
  ฟังก์ชัน GenerateRandomGraphs() รับ 'e' เป็นจำนวน edge
  กำหนด i = 0
  while (i < e)
    edge[i][0] = rand() % N + 1
    edge[i][1] = rand() % N + 1
    เพิ่ม i
  สำหรับ i = 0 ถึง N-1
    กำหนด count = 0
    สำหรับ j = 0 ถึง e-1
      ถ้า (edge[j][0] == i+1)
        พิมพ์ edge[j][1]
        เพิ่ม count
      มิฉะนั้นถ้า (edge[j][1] == i+1)
        พิมพ์ edge[j][0]
        เพิ่ม count
      มิฉะนั้นถ้า (j == e-1 && count == 0)
        พิมพ์ "Isolated Vertex"
    จบลูป
  จบลูป
สิ้นสุด

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

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

void GenerateRandomGraphs(int e) {
    int i, j, edge[e][2], count;
    i = 0;
    // สร้างการเชื่อมต่อระหว่างสองตัวเลขสุ่ม
    while (i < e) {
        edge[i][0] = rand() % N + 1;
        edge[i][1] = rand() % N + 1;
        i++;
    }
    // พิมพ์การเชื่อมต่อของแต่ละโหนด ไม่สนทิศทาง
    cout << "\nThe generated random graph is: ";
    for (i = 0; i < N; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for (j = 0; j < e; 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 == e-1 && count == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
}

int main() {
    int n, i, e;
    cout << "Enter the number of edges for the random graphs: ";
    cin >> e;
    GenerateRandomGraphs(e);
    return 0;
}

ผลลัพธ์

Enter the number of edges for the random graphs: 10
The generated random graph is:
1-> { 10 7 }
2-> { 10 }
3-> { 7 8 7 }
4-> { 7 6 7 }
5-> { Isolated Vertex! }
6-> { 8 4 }
7-> { 4 3 4 1 3 }
8-> { 6 3 }
9-> { Isolated Vertex! }
10-> { 2 1 }