इस प्रोग्राम में रैंडम वर्टेक्स और एज के लिए एक रैंडम ग्राफ जनरेट किया जाता है। इस प्रोग्राम की समय जटिलता O(v * e) है। जहां v वर्टेक्स की संख्या है और e एज की संख्या है।
एल्गोरिदम
Begin एक फंक्शन GenRandomGraphs() विकसित करें, जिसमें 'e' एज की संख्या और 'v' वर्टेक्स की संख्या आर्गुमेंट लिस्ट में हो। rand() फंक्शन का उपयोग करके ग्राफ के वर्टेक्स और एज की संख्या को रैंडम मान असाइन करें। प्रत्येक वर्टेक्स के कनेक्शन प्रिंट करें, दिशा की परवाह किए बिना। जिस वर्टेक्स की डिग्री नहीं है उसके लिए "Isolated vertex" प्रिंट करें। End
उदाहरण
#include<iostream> #include<stdlib.h> using namespace std; void GenRandomGraphs(int NOEdge, int NOVertex) { int i, j, edge[NOEdge][2], count; i = 0; //rand() का उपयोग करके ग्राफ के वर्टेक्स और एज की संख्या को रैंडम मान असाइन करें। 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!"; //जिस वर्टेक्स की डिग्री नहीं है उसके लिए "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 }
