이 프로그램은 사용자가 입력한 정점(vertex)의 개수와 간선(edge)의 개수를 바탕으로 무작위(random) 무방향 그래프를 생성하고, 각 정점의 연결 상태를 출력합니다. 자기 루프(self-loop)와 중복 간선을 자동으로 걸러내므로, 유효한 단순 그래프가 만들어집니다.
입력
그래프를 구성할 정점의 개수와 간선의 개수를 순서대로 입력받습니다.
출력
생성된 그래프의 각 정점 번호와 해당 정점에 연결된 이웃 정점들의 목록을 출력합니다. 어떤 간선에도 연결되지 않은 정점은 "고립 정점(isolated vertex)"으로 표시됩니다.
알고리즘
Begin
RandomGraphs() 함수를 선언한다.
정수형 매개변수 NoEdge(간선 수), NoVertex(정점 수)를 받는다.
정수형 변수 i, j, e[NoEdge][2], c를 선언한다.
i = 0으로 초기화한다.
while (i < NoEdge) 동안 반복:
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++
"무작위로 생성된 그래프:" 출력
for(i = 0 ~ NoVertex-1)
c = 0
"정점 번호"와 정점 번호 출력
for(j = 0 ~ NoEdge-1)
if(e[j][0] == i+1)이면
e[j][1] 값 출력, c++
else if(e[j][1] == i+1)이면
e[j][0] 값 출력, c++
else if(j == NoEdge-1 && c == 0)이면
"이 정점은 고립되었습니다!!!" 출력
End
Begin
정수형 변수 edg, ver을 선언한다.
"무작위 그래프 생성:" 출력
"그래프의 정점 개수를 입력하세요:" 출력 후 ver에 입력받는다.
"그래프의 간선 개수를 입력하세요:" 출력 후 edg에 입력받는다.
RandomGraphs(edg, ver)를 호출하여 edg개의 간선과 ver개의 정점을 가진
무작위 무방향 그래프를 생성한다.
End예제 코드
#include<iostream>
#include<stdlib.h>
using namespace std;
void RandomGraphs(int NoEdge, int NoVertex) { // 무작위 그래프 생성
int i, j, e[NoEdge][2], c;
i = 0;
while(i < NoEdge) { // 두 정점 사이의 연결 생성
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<<"무작위로 생성된 그래프: \n";
for(i = 0; i < NoVertex; i++) { // 그래프 출력
c = 0;
cout<<"정점 번호 "<<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<<"이 정점은 고립되었습니다!!!";
}
cout<<" }\n";
}
}
int main() {
int edg, ver;
cout<<"무작위 그래프 생성: ";
// 정점과 간선의 개수를 입력받습니다.
cout<<"\n그래프의 정점 개수를 입력하세요: ";
cin>>ver;
cout<<"\n그래프의 간선 개수를 입력하세요: ";
cin>>edg;
RandomGraphs(edg, ver); // edg개의 간선과 ver개의 정점을 가진 무작위 무방향 그래프 생성 함수 호출
}실행 결과
무작위 그래프 생성:
그래프의 정점 개수를 입력하세요: 5
그래프의 간선 개수를 입력하세요: 5
무작위로 생성된 그래프:
정점 번호 1: { 5 3 }
정점 번호 2: { 3 5 }
정점 번호 3: { 2 5 1 }
정점 번호 4: { 이 정점은 고립되었습니다!!! }
정점 번호 5: { 1 3 2 }핵심 포인트
- 난수 생성:
rand()%NoVertex+1을 사용해 1부터 정점 개수까지 범위 안에서 정점 번호를 무작위로 선택합니다. - 자기 루프 방지: 무작위로 선택한 두 정점이 서로 같으면(
e[i][0] == e[i][1]) 해당 간선을 버리고 다시 시도합니다. - 중복 간선 방지: 이미 생성된 간선과 동일한 연결인지 양방향으로 모두 검사하여, 같은 간선이 중복 저장되지 않도록 합니다.
- 고립 정점 처리: 어떤 간선에도 등장하지 않는 정점은 별도의 메시지로 알려줍니다.
참고로 배열 e[NoEdge][2]는 가변 길이 배열(VLA)로, 표준 C++ 문법은 아니지만 GCC나 Clang 컴파일러에서는 확장 기능으로 컴파일됩니다. 표준을 엄격하게 지키려면 std::vector<std::array<int,2>> 등을 사용하는 것이 좋습니다. 또한 간선 개수가 많아질수록 중복 검사 비용이 증가하므로, 대규모 그래프에는 인접 행렬이나 집합(set)을 활용한 검사가 더 효율적입니다.