โปรแกรม C++ สร้างกราฟสุ่มด้วยการสร้างขอบสุ่ม

ในโปรแกรมนี้จะสร้างกราฟสุ่มสำหรับโหนดและขอบสุ่ม ความซับซ้อนด้านเวลาคือ 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 }