[TestRandomGraph.cpp]
/*
(1)정점의 수와 간선의 수를 입력하면 무작위로 그래프를 발생시키는 함수를 구현하라.
단, 정점 사이에 중복된 간선이 존재하지 않아야 한다. 생성된 그래프를 화면에 출력하고, 파일에 저장하라.
정점의 이름은 'A'로부터 시작하여 하나씩 증가시키도록 한다.
(2) (1)을 이용하여 무작위로 그래프를 발생시키고 프로그램 11.13의 연결 성분 탐색을 참고하여 연결된 성분의 개수를 출력하라
(3) (1) 알고리즘을 보완하여 모든 정점이 연결된 "연결 그래프"를 무작위로 발생시키는 다음 함수를 구현한다.
(2) 와 같이 연결된 성분의 개수가 1이 되는지 확인한다.
*/
#include "ConnectedComponentGraph.h"
int main(void)
{
ConnectedComponentGraph g, g2;
int numVtx, numEdge;
srand((unsigned)time(NULL));
cout << "정점의 개수 입력: ";
cin >> numVtx;
do
{
cout << "간선의 개수 입력:(정점의 개수 두배를 넘어서면 안된다) ";
cin >> numEdge;
} while (numEdge > 2 * numVtx);
g.randomGraph(numVtx, numEdge);
cout << "그래프 출력" << endl;
g.display();
g.store("graph.txt");
cout << endl << "연결 성분 테스트 그래프" << endl;
g.resetVisited();
g.findConnectedComponent();
cout << endl << endl << "연결 그래프 생성" << endl;
g2.randomConnectedGraph(numVtx);
cout << endl << "연결 성분 테스트 그래프" << endl;
g2.resetVisited();
g2.findConnectedComponent();
return 0;
}
[AdjMatGraph.h]
/*
인접 행렬을 이용한 그래프 클래스 프로그램
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
#define MAX_VTXS 256 //표현 가능한 최대 정점의 개수
class AdjMatGraph
{
protected:
int size; //정점의 개수
char vertices[MAX_VTXS]; //정점의 이름
int adj[MAX_VTXS][MAX_VTXS]; //인접 행렬
public:
AdjMatGraph()
{
reset();
}
char getVertex(int i)
{
return vertices[i];
}
int getEdge(int i, int j)
{
return adj[i][j];
}
void setEdge(int i, int j, int val)
{
adj[i][j] = val;
}
bool isEmpty()
{
return size == 0;
}
bool isFull()
{
return size >= MAX_VTXS;
}
//그래프 초기화==>공백 상태의 그래프
void reset()
{
size = 0;
for (int i = 0; i < MAX_VTXS; i++)
for (int j = 0; j < MAX_VTXS; j++)
setEdge(i, j, 0);
}
//정점 삽입 연산
void insertVertex(char name)
{
if (!isFull())
vertices[size++] = name;
else
cout << "Error: 그래프 정점 개수 초과" << endl;
}
//간선 삽입 연산: 무방향 그래프의 경우
void insertEdge(int u, int v)
{
setEdge(u, v, 1);
setEdge(v, u, 1); //방향 그래프에서는 삭제
}
//무작위로 그래프를 발생시키는 함수
void randomGraph(int numVtx, int numEdge)
{
int i = 0;
for (int j = 0; j < numVtx; j++)
insertVertex('A'+j);
while (i < numEdge)
{
int count = 0;
do
{
int first = rand() % numVtx;
int second;
do
{
second = rand() % numVtx;
} while (first == second);
if (!adj[first][second])
{
insertEdge(first, second);
count++;
}
} while (!count);
i++;
}
}
//모든 정점이 연결된 "연결 그래프"를 무작위로 발생시키는 함수
void randomConnectedGraph(int numVtx)
{
for (int j = 0; j < numVtx; j++)
insertVertex('A' + j);
for (int i = 0; i < numVtx; i++)
for (int j = 0; j < numVtx; j++)
if (i != j)
insertEdge(i, j);
}
//그래프 정보 출력
void display(FILE *fp = stdout)
{
fprintf(fp, "%d\n", size);
for (int i = 0; i < size; i++)
{
fprintf(fp, "%c ", getVertex(i));
for (int j = 0; j < size; j++)
fprintf(fp, " %3d", getEdge(i, j));;
fprintf(fp, "\n");
}
}
//파일 입력 함수
void load(char *filename)
{
FILE *fp = fopen(filename, "r");;
if (fp != NULL)
{
int n, val;
fscanf(fp, "%d", &n); //정점의 전체 개수
for (int i = 0; i < n; i++)
{
char str[80];
fscanf(fp, "%s", str);
insertVertex(str[0]);
for (int j = 0; j < n; j++)
{
int val;
fscanf(fp, "%d", &val);
if (val != 0)
insertEdge(i, j);
}
}
fclose(fp);
}
}
//파일 저장 함수
void store(char *filename)
{
FILE *fp = fopen(filename, "w");
if (fp != NULL)
{
display(fp);
fclose(fp);
}
}
};
[SrchAMGraph.h]
/*
탐색 기능을 가진 그래프 클래스(인접 행렬 사용)
*/
#include "AdjMatGraph.h"
#include "CircularQueue.h"
class SrchAMGraph :public AdjMatGraph
{
protected:
bool visited[MAX_VTXS]; //정점의 방문 정보
public:
void resetVisited() //모든 정점을 방문하지 않았다고 설정
{
for (int i = 0; i < size; i++)
visited[i] = false;
}
bool isLinked(int u, int v)
{
return getEdge(u, v) != 0;
}
//깊이 우선 탐색 함수
void DFS(int v)
{
visited[v] = true;
cout << getVertex(v) << " ";
for (int w = 0; w < size; w++)
if (isLinked(v, w) && visited[w] == false)
DFS(w); //연결+방문X=> 순환 호출로 방문
}
//인접행렬로 표현된 그래프에 대한 너비우선탐색 연산
void BFS(int v)
{
visited[v] = true;
cout << getVertex(v) << " "; //정점의 이름 출력
CircularQueue que;
que.enqueue(v); //시작 정점을 큐에 저장
while (!que.isEmpty())
{
int v = que.dequeue(); //큐에 정점 추출
for (int w = 0; w < size; w++)
if (isLinked(v, w) && visited[w] == false)
{
visited[w] = true; //방문 표시
cout << getVertex(w) << " ";
que.enqueue(w);
}
}
}
};
[ConnectedComponentGraph.h]
/*
인접 배열을 이용한 그래프의 연결 성분 탐색 프로그램
*/
#include "SrchAMGraph.h"
class ConnectedComponentGraph :public SrchAMGraph
{
private:
int label[MAX_VTXS]; //정점의 색상 필드 추가
public:
//깊이 우선 탐색
void labelDFS(int v, int color)
{
visited[v] = true;
label[v] = color;
for (int w = 0; w < size; w++)
if (isLinked(v, w) && visited[w] == false)
labelDFS(w, color);
}
//그래프의 연결 성분 검출 함수
void findConnectedComponent()
{
int count = 0;
for (int i = 0; i < size; i++)
if (visited[i] == false)
labelDFS(i, ++count);
cout << "그래프의 연결 성분 개수==" << count << endl;
for (int i = 0; i < size; i++)
cout << getVertex(i) << "=" << label[i] << " ";
cout << endl;
}
};
[1+2번 문제]
[3번 문제]
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
[참고] C++로 쉽게 풀어쓴 자료구조
'C++ > C++로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 12장 Kruskal & Prim 알고리즘 예제 (1) | 2017.11.21 |
|---|---|
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 11 (2) (0) | 2017.11.16 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 10 (2) | 2017.11.10 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9 (2) (0) | 2017.11.01 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 9 (1) (0) | 2017.10.31 |