생각보다 오류가 많은데 정오표에도 기제되어있지 않아 직접 포스팅합니다.
[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);
}
}
};
[WGraph.h]
/*
인접 행렬로 구현된 가중치 그래프 클래스
*/
#include "AdjMatGraph.h"
#define INF 9999 //값이 INF 이상이면 간선이 없음
class WGraph :public AdjMatGraph //AdjMatGraph 상속
{
public:
void insertEdge(int u, int v, int weight)
{
if (weight > INF)
weight = INF;
setEdge(u, v, weight);
}
bool hasEdge(int i, int j)
{
return (getEdge(i, j) < INF);
}
void load(char *filename)
{
FILE *fp = fopen(filename, "r");
if (fp != NULL)
{
int n;
fscanf(fp, "%d", &n);
for (int i = 0; i < n; i++)
{
char str[80];
int val;
fscanf(fp, "%s", str);
insertVertex(str[0]); //정점 삽입
for (int j = 0; j < n; j++)
{
fscanf(fp, "%d", &val); //간선 정보
insertEdge(i, j, val); //간선 삽입
}
}
fclose(fp);
}
}
};
[VertexSets.h]
/*
Union-Find 연산을 위한 정점 집합 클래스 구현
*/
#define MAX_VTXS 256
class VertexSets
{
private:
int parent[MAX_VTXS]; //부모 정점의 id
int nSets; //집합의 개수
public:
VertexSets(int n) :nSets(n)
{
for (int i = 0; i < nSets; i++)
parent[i] = -1;
}
bool isRoot(int i)
{
return parent[i] < 0;
}
int findSet(int v) //v가 속한 집합을 찾아 반환
{
while (!isRoot(v))
v = parent[v];
return v;
}
void unionSets(int s1, int s2) //집합 s1을 집합 s2에 합침
{
parent[s1] = s2;
nSets--;
}
};
[kruskalHeapNode.h]
/*
Kruskal의 최소 비용 신장 트리 프로그램
*/
#include <iostream>
using namespace std;
class HeapNode
{
private:
int key; //Key 값: 간선의 가중치
int v1; //정점 v1
int v2; //정점 2
public:
HeapNode(int k=0, int u= -1, int v = -1) :key(k), v1(u), v2(v)
{
}
void setKey(int k, int u, int v)
{
key = k;
v1 = u;
v2 = v;
}
int getKey()
{
return key;
}
int getV1()
{
return v1;
}
int getV2()
{
return v2;
}
};
[kruskalMinHeap.h]
/*
크루스칼 알고리즘을 위한 최소 힙 클래스
*/
#include "kruskalHeapNode.h"
#define MAX_ELEMENT 200
class MinHeap
{
private:
HeapNode node[MAX_ELEMENT]; //요소의 배열
int size; //힙의 현재 요소의 개수
public:
MinHeap() :size(0)
{
}
bool isEmpty()
{
return size == 0;
}
bool isFull()
{
return size == MAX_ELEMENT - 1;
}
HeapNode &getParent(int i)
{
return node[i / 2];
}
HeapNode &getLeft(int i)
{
return node[i * 2];
}
HeapNode &getRight(int i)
{
return node[i * 2 + 1];
}
//삽입 함수
void insert(int key, int u, int v)
{
if (isFull())
return;
int i = ++size;
while (i != 1 && key < getParent(i).getKey())
{
node[i] = getParent(i);
i /= 2;
}
node[i].setKey(key, u, v);
}
//삭제 함수
HeapNode remove()
{
if (isEmpty())
return NULL;
HeapNode root = node[1];
HeapNode last = node[size--];
int parent = 1;
int child = 2;
while (child <= size)
{
if (child<size && getLeft(parent).getKey()>getRight(parent).getKey())
child++;
if (last.getKey() <= node[child].getKey())
break;
node[parent] = node[child];
parent = child;
child *= 2;
}
node[parent] = last;
return root;
}
};
[WGraphMST.h]
/*
Kruskal과 Prim의 최소 비용 신장 트리 프로그램
*/
#include "kruskalMinHeap.h"
#include "WGraph.h"
#include "VertexSets.h"
class WGraphMST :public WGraph
{
public:
void Kruskal() //kruskal의 최소 비용 신장 트리 프로그램
{
MinHeap heap;
//힙에 모든 간선 삽입
for (int i = 0; i < size - 1; i++)
for (int j = i + 1; j < size; j++)
if (hasEdge(i, j))
heap.insert(getEdge(i, j), i, j);
VertexSets set(size); //size개의 집합을 만듬
int edgeAccepted = 0; //선택된 간선의 수
while (edgeAccepted < size - 1)
{
HeapNode &e = heap.remove(); //최소 힙에서 삭제
int uset = set.findSet(e.getV1()); //정점 u의 집합 번호
int vset = set.findSet(e.getV2()); //정점 v의 집합 번호
if (uset != vset) //서로 속한 집합이 다르면
{
cout << "간선추가: " << getVertex(e.getV1()) << " - " << getVertex(e.getV2()) << " (비용: " << e.getKey() << ")" << endl;
set.unionSets(uset, vset); //두개의 집합을 합함
edgeAccepted++;
}
}
}
//MST에 포함되지 않은 정점들 중에서 MST와의 거리가 최소인 정점 선택
int getMinVertex(bool *selected, int *dist)
{
int minv = 0;
int mindist = INF;
for (int v = 0; v < size; v++)
if (!selected[v] && dist[v] < mindist)
{
mindist = dist[v];
minv = v;
}
return minv;
}
//Prim의 최소 비용 신장 트리 프로그램
void Prim(int s)
{
bool selected[MAX_VTXS]; //정점이 이미 포함
int dist[MAX_VTXS]; //거리
for (int i = 0; i < size; i++) //배열 초기화
{
dist[i] = INF;
selected[i] = false;
}
dist[s] = 0; //시작 정점
for (int i = 0; i < size; i++)
{
//포함되지 않은 정점들 중에서 MST와의 거리가 최소인 정점
int u = getMinVertex(selected, dist);
selected[u] = true;
if (dist[u] == INF)
return;
cout << (char)getVertex(u) << " ";
for (int v = 0; v < size; v++)
if (getEdge(u, v) != INF)
if (!selected[v] && getEdge(u, v) < dist[v])
dist[v] = getEdge(u, v);
}
cout << endl;
}
};
#include "WGraphMST.h"
#include "WGraphMST.h"
int main(void)
{
WGraphMST g;
g.load("graph.txt");
//cout << "MST By Kruskal's Algorithm" << endl;
//g.Kruskal();
cout << "MST By Prim's Algorithm" << endl;
g.Prim(0);
return 0;
}
[graph.txt]
[Kruskal]
[Prim]
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
[참고] C++로 쉽게 풀어쓴 자료구조
'C++ > C++로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 12 (0) | 2017.11.24 |
|---|---|
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 12장 Dijkstra & Floyd 알고리즘 예제 (0) | 2017.11.23 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 11 (2) (0) | 2017.11.16 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 11 (1) (3) | 2017.11.15 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 10 (2) | 2017.11.10 |