特定の次数シーケンスに対してグラフを作成できるかどうかを確認するC++プログラム

与えられた次数の順序でグラフが作成される可能性をチェックするプログラムです。

入力

エッジと頂点は必要ありません。

出力

作成されたグラフのランダムな値が表示されます。

アルゴリズム

Begin
   Declare a function RandomGraphs().
      Declare NoEdge and NoVertex of the integer datatype and pass them as parameter.
      Declare i, j, e[NoEdge][2], c of the integer datatype.
      Initialize i = 0.
      while (i < NoEdge) do
         e[i][0] = rand()%NoVertex+1.
         e[i][1] = rand()%NoVertex+1.
         if(e[i][0] == e[i][1]) then
            continue.
         else
            for(j = 0; j < i; j++)
            if((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0])) then
               i--.
               i++.
            Print “The randomly generated graph:”.
      for(i = 0 to NoVertex-1)
      c = 0;
      Print "Vertex number ".
      Print the number of vertex.
      for(j = 0 to NoEdge-1)
         if(e[j][0] == i+1) then
            Print the value of e[j][1].
            c++.
         else if(e[j][1] == i+1) then
            Print the value of e[j][0].
            c++.
         else if(j == NoEdge-1 and c == 0) then
            Print "This vertex is isolated!!!".
End
Begin
   Declare edg, ver of the integer datatype.
   Print "generation of a random graph: ".
   Print "Enter the number of vertexes for the graph: ".
   Take input of the value of ver variable.
   Print "Enter the number of edges for the graph: ".
   Take input of the value of edg variable.
   Call RandomGraphs(edg, ver) to generate a random undirected graph with edg edges and ver vertexes.
End.

例

#include<iostream>
#include<stdlib.h>
using namespace std;
void RandomGraphs(int NoEdge, int NoVertex) { // generate random graph.
   int i, j, e[NoEdge][2], c;
   i = 0;
   while(i < NoEdge) { // Build a connection between two vertexes
      e[i][0] = rand()%NoVertex+1;
      e[i][1] = rand()%NoVertex+1;
      if(e[i][0] == e[i][1])
         continue;
      else {
         for(j = 0; j < i; j++) {
            if((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0]))
            i--;
         }
      }
      i++;
   }
   cout<<"The randomly generated graph: \n";
   for(i = 0; i < NoVertex; i++) { // printing the graph
      c = 0;
      cout<<"Vertex number "<<i+1<<": \t { ";
      for(j = 0; j < NoEdge; j++) {
         if(e[j][0] == i+1) {
            cout<<e[j][1]<<" ";
            c++;
         } else if(e[j][1] == i+1) {
            cout<<e[j][0]<<" ";
            c++;
         } else if(j == NoEdge-1 && c == 0)
            cout<<"This vertex is isolated!!!";
      }
      cout<<" }\n";
   }
}
int main() {
   int edg, ver;
   cout<<"generation of a random graph: ";
   // Take the input of the vertex and edges.
   cout<<"\nEnter the number of vertexes for the graph: ";
   cin>>ver;
   cout<<"\nEnter the number of edges for the graph: ";
   cin>>edg;
   RandomGraphs(edg, ver); // Call function to generate a random undirected graph with edg edges and ver vertexes.
}

出力

generation of a random graph:
Enter the number of vertexes for the graph: 5

Enter the number of edges for the graph: 5
The randomly generated graph:
Vertex number 1: { 5 3 }
Vertex number 2: { 3 5 }
Vertex number 3: { 2 5 1 }
Vertex number 4: { This vertex is isolated!!! }
Vertex number 5: { 1 3 2 }