이 프로그램은 무작위로 선택된 정점과 간선을 이용해 랜덤 그래프를 생성합니다. 프로그램의 시간 복잡도는 O(v×e)이며, 여기서 v는 정점(vertex)의 개수, e는 간선(edge)의 개수를 의미합니다.
알고리즘
시작
간선의 개수 'e'와 정점의 개수 'v'를 매개변수로 받는
GenRandomGraphs() 함수를 작성한다.
rand() 함수를 사용해 그래프의 정점 수와 간선 수에
임의의 값을 할당한다.
방향에 관계없이 각 정점의 연결 정보를 출력한다.
차수가 0인 정점(고립된 정점)에는 "Isolated vertex"를 출력한다.
끝
프로그램 동작 방식
간선을 하나씩 생성할 때마다 먼저 두 끝점이 같은 경우(자기 자신을 연결하는 셀프 루프)를 제외하고, 이전에 생성된 간선들과 중복되는지 검사합니다. 중복이 발견되면 해당 간선을 다시 추첨하여 그래프에 서로 다른 간선만 포함되도록 합니다. 모든 간선이 확정되면 각 정점별로 연결된 이웃 정점 목록을 출력하며, 연결된 간선이 하나도 없는 정점은 "Isolated Vertex!"로 표시됩니다.
예제 코드
#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 }
핵심 포인트 정리
- 시간 복잡도: O(v×e) — 정점 수와 간선 수에 비례하여 실행 시간이 증가합니다.
- 중복 간선 방지: 새로 생성한 간선이 기존 간선과 동일하면(방향 무관) 다시 추첨합니다.
- 셀프 루프 제거: 시작 정점과 끝 정점이 같은 간선은 생성하지 않습니다.
- 최대 간선 수: n개의 정점을 가진 단순 그래프가 가질 수 있는 최대 간선 수는 n(n−1)/2이며, 이 범위 안에서 간선 개수가 결정됩니다.
- 고립 정점 처리: 어떤 간선에도 포함되지 않은 정점은 명확히 표시되어 그래프 구조를 한눈에 파악할 수 있습니다.