โปรแกรม C++ สร้าง Random Directed Acyclic Graph (DAG) สำหรับจำนวนขอบที่กำหนด

ในโปรแกรมนี้เราสร้าง random directed acyclic graph สำหรับขอบ 'e' ที่กำหนด Time complexity คือ O(e*v*e)

อัลกอริทึม

เริ่มต้น
  ฟังก์ชัน GenerateRandomGraphs() มี 'e' เป็นจำนวนขอบใน argument list
  สร้างการเชื่อมต่อระหว่างตัวเลขสุ่ม 2 ตัว สำหรับกรณีตัวอย่าง จำกัดจำนวน vertex ไว้ที่ 20
  ตรวจสอบ cycle ในกราฟโดยใช้ CheckAcyclic()
    ถ้าคืนค่า false ให้ทิ้งขอบนี้
    ไม่เช่นนั้น เก็บขอบนี้ไว้ในกราฟ
  พิมพ์การเชื่อมต่อแบบมีทิศทางของแต่ละ vertex
  ถ้า in+out degree ของแต่ละ vertex เป็นศูนย์ ให้พิมพ์ vertex นั้นเป็น "isolated vertex"
สิ้นสุด

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

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

bool Checkcyclic(int ed[][2], int edge, bool check[], int v) {
    int i;
    if(check[v] == true) {
        return false;
    } else {
        check[v] = true;
        for(i = edge; i >= 0; i--) {
            if(ed[i][0] == v) {
                return Checkcyclic(ed, edge, check, ed[i][1]);
            }
        }
    }
    check[v] = false;
    if(i == 0)
        return true;
}

void GenerateRandomGraphs(int e) {
    int i, j, ed[e][2], count;
    bool c[11];
    i = 0;
    while(i < e) {
        ed[i][0] = rand() % N + 1;
        ed[i][1] = rand() % N + 1;
        for(j = 1; j <= 10; j++)
            c[j] = false;
        if(Checkcyclic(ed, i, c, ed[i][0]) == true)
            i++;
    }
    cout << "\nThe generated random random graph is: ";
    for(i = 0; i < N; i++) {
        count = 0;
        cout << "\n\t" << i+1 << "-> { ";
        for(j = 0; j < e; j++) {
            if(ed[j][0] == i+1) {
                cout << ed[j][1] << " ";
                count++;
            } else if(ed[j][1] == i+1) {
                count++;
            } else if(j == e-1 && count == 0)
                cout << "Isolated Vertex!";
        }
        cout << " }";
    }
}

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

ผลลัพธ์ตัวอย่าง

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