이 글에서는 사용자가 입력한 간선의 개수 'e'를 바탕으로 무방향 랜덤 그래프(undirected random graph)를 생성하는 C++ 프로그램을 소개합니다. 랜덤 그래프 생성은 대규모 네트워크 시뮬레이션이나 그래프 알고리즘용 테스트 데이터를 만들 때 널리 활용되는 기법입니다.
간선을 생성하는 단계는 두 개의 난수를 뽑아 하나의 간선으로 연결하는 작업의 반복이므로 O(e)의 시간이 걸리며, 각 정점의 연결 상태를 모두 출력하는 단계는 정점마다 전체 간선 목록을 훑어야 하므로 전체적으로 O(N × e)의 시간 복잡도를 가집니다.
알고리즘
시작
함수 GenerateRandomGraphs(): 간선의 개수 'e'를 매개변수로 받는다.
i = 0으로 초기화
while(i < e)
edge[i][0] = rand()%N + 1
edge[i][1] = rand()%N + 1
i 증가
i = 0부터 N-1까지 반복
count = 0으로 초기화
j = 0부터 e-1까지 반복
만약 edge[j][0] == i+1이면
edge[j][1]을 출력하고 count 증가
아니면 edge[j][1] == i+1이면
edge[j][0]을 출력하고 count 증가
아니면 j == e-1이고 count == 0이면
"Isolated Vertex"(고립된 정점) 출력
종료
예제 코드
#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;
void GenerateRandomGraphs(int e) {
int i, j, edge[e][2], count;
i = 0;
// 두 난수 사이의 연결을 생성한다. 예제를 단순하게 하기 위해 정점 수를 10개로 제한한다.
while(i < e) {
edge[i][0] = rand()%N+1;
edge[i][1] = rand()%N+1;
i++;
}
// 방향과 관계없이 각 정점의 모든 연결을 출력한다.
cout<<"\nThe generated random graph is: ";
for(i = 0; i < N; i++) {
count = 0;
cout<<"\n\t"<<i+1<<"-> { ";
for(j = 0; j < e; j++) {
if(edge[j][0] == i+1) {
cout<<edge[j][1]<<" ";
count++;
}
else if(edge[j][1] == i+1) {
cout<<edge[j][0]<<" ";
count++;
}
// 차수가 0인 정점에 대해 "Isolated Vertex"를 출력한다.
else if(j == e-1 && count == 0)
cout<<"Isolated Vertex!";
}
cout<<" }";
}
}
int main() {
int n, i ,e;
cout<<"Enter the number of edges for the random graphs: ";
cin>>e;
GenerateRandomGraphs(e);
}
실행 결과
Enter the number of edges for the random graphs: 10
The generated random graph is:
1-> { 10 7 }
2-> { 10 }
3-> { 7 8 7 }
4-> { 7 6 7 }
5-> { Isolated Vertex! }
6-> { 8 4 }
7-> { 4 3 4 1 3 }
8-> { 6 3 }
9-> { Isolated Vertex! }
10-> { 2 1 }
코드 핵심 포인트
- 난수 정점 생성:
rand() % N + 1을 사용해 1부터 N 사이의 임의의 정점 번호 두 개를 뽑아 하나의 간선으로 연결합니다. - 무방향 그래프 처리: 각 간선의 양쪽 끝점을 모두 검사하므로, 연결 관계가 양방향으로 함께 출력됩니다. 예를 들어 1번 정점에 10이 있다면 10번 정점에도 1이 나타납니다.
- 고립 정점(Isolated Vertex) 표시: 어떤 간선에도 연결되지 않아 차수가 0인 정점은 "Isolated Vertex!"로 출력됩니다. 위 실행 결과에서 5번과 9번 정점이 해당됩니다.
- 중복 간선 주의: 이 코드는 이미 존재하는 간선이나 자기 루프(self-loop)에 대한 검사를 수행하지 않으므로, 실행 결과처럼 같은 연결이 여러 번 나타날 수 있습니다. 필요하다면 간선 생성 단계에서 중복 검사 로직을 추가하면 됩니다.
- 난수 시드 초기화: 프로그램을 실행할 때마다 같은 그래프가 생성되는 것을 피하려면
main()함수 시작 부분에서srand(time(NULL))을 호출해 난수 시드를 초기화하는 것이 좋습니다.