C++ 랜덤 에지 생성으로 무작위 그래프 생성하기

이 프로그램은 임의의 정점(vertex)과 간선(edge)을 이용해 랜덤 그래프를 생성합니다. 프로그램의 시간 복잡도는 O(v × e)이며, 여기서 v는 정점의 개수, e는 간선의 개수를 의미합니다.

동작 원리

• 정점·간선 개수 결정: rand() 함수를 사용해 그래프의 정점 개수와 간선 개수를 무작위로 정합니다.
• 간선 생성: 두 정점 번호를 무작위로 뽑아 간선으로 연결하되, 자기 자신에게 연결되는 셀프 루프(self-loop)와 중복 간선은 제외합니다.
• 연결 정보 출력: 방향에 관계없이 각 정점에 연결된 다른 정점들을 출력합니다.
• 고립 정점 처리: 연결된 간선이 하나도 없는 정점은 "Isolated Vertex(고립된 정점)"로 표시합니다.

알고리즘

Begin
    간선의 개수 'e'와 정점의 개수 'v'를 인자로 받는
    GenRandomGraphs() 함수를 작성한다.
    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!"; //차수가 없는 정점에 고립 정점임을 출력한다.
      }
      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);
}

코드 설명

• GenRandomGraphs() 함수는 2차원 배열 edge[NOEdge][2]에 각 간선의 양 끝 정점 번호를 무작위로 저장합니다.
• 두 정점 번호가 같으면 셀프 루프이므로 해당 간선을 버리고 새로 뽑습니다.
• 이미 저장된 간선들과 양방향 모두 비교하여 중복 간선을 제거합니다.
• 마지막 반복문에서는 각 정점을 기준으로 연결된 정점 목록을 출력하고, 연결된 간선이 없으면 고립 정점으로 표시합니다.

출력 결과

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 }

rand() 함수의 반환값이 실행할 때마다 달라지므로, 정점 개수·간선 개수·연결 형태 역시 매번 다르게 나타납니다. 따라서 위 출력 결과는 어디까지나 한 번의 실행 예시입니다.