가중치를 가지는 무방향 그래프의 최소신장트리를 생성하는 코드이다.
[Class] Vertex , Edge
template <typename T>
class Vertex {
public:
T value;
int key;
Vertex(int _key, T _value) : key(_key), value(_value) {};
void print(){
std::cout << "(" << key << ", " << value << ")" << std::endl;
}
bool operator>(const Vertex<T> arg) const {
return this -> key > arg.key;
}
bool operator>(const int arg) const {
return this -> key > arg;
}
bool operator<(const Vertex<T> arg) const {
return this -> key < arg.key;
}
bool operator<(const int arg) const {
return this -> key < arg;
}
bool operator==(const Vertex<T> arg) const {
return this -> key == arg.key;
}
bool operator==(const int arg) const {
return this -> key == arg;
}
};
template <typename T>
class Edge {
public:
Vertex<T> *vert1, *vert2;
int weight;
Edge(Vertex<T> *_vert1, Vertex<T> *_vert2, int _weight) : vert1(_vert1), vert2(_vert2), weight(_weight) {};
bool operator<(const Edge<T> arg) const {
return this -> weight < arg.weight;
}
bool operator>(const Edge<T> arg) const {
return this -> weight > arg.weight;
}
void print(){
std::cout << "(" << vert1 -> key << ", " << vert1 -> value << ")--" << weight << "--(" << vert2 -> key << ", " << vert2 -> value << ")" << std::endl;
}
};
정점을 key와 value로 구성하게 하였다. 모든 연산 기준은 key값이다.
[Class] Graph
template <typename T>
class Graph {
public:
Edge<T> **edgeList;
Vertex<T> **vertList;
int edgeCnt, vertCnt;
Graph() {
edgeList = new Edge<T>*[VERT_MAX * VERT_MAX];
vertList = new Vertex<T>*[VERT_MAX];
edgeCnt = vertCnt = 0;
}
Graph(const Graph<T> &origin) : Graph() {
copy(origin);
}
~Graph(){
for(int i = 0; i < edgeCnt; i++) delete edgeList[i];
for(int i = 0; i < vertCnt; i++) delete vertList[i];
delete edgeList;
delete vertList;
}
Graph<T> operator=(const Graph<T>& arg) {
for(int i = 0; i < edgeCnt; i++) delete edgeList[i];
for(int i = 0; i < vertCnt; i++) delete vertList[i];
edgeCnt = vertCnt = 0;
copy(arg);
return *this;
}
void copy(const Graph<T> &origin) {
for(int i = 0; i < origin.vertCnt; i++)
add_vert(origin.vertList[i] -> key, origin.vertList[i] -> value);
for(int i = 0; i < origin.edgeCnt; i++)
add_edge(vertList[origin.edgeList[i] -> vert1 -> key],
vertList[origin.edgeList[i] -> vert2 -> key], origin.edgeList[i] -> weight);
}
void add_vert(int key, T value) {
vertList[vertCnt++] = new Vertex<T>(key, value);
}
void add_edge(Vertex<T> *vert1, Vertex<T> *vert2, int weight) {
edgeList[edgeCnt++] = new Edge<T>(vert1, vert2, weight);
}
void add_edge(int key1, int key2, int weight) {
edgeList[edgeCnt++] = new Edge<T>(vertList[key1], vertList[key2], weight);
}복사생성자와 대입연산자를 추가로 구현하였다.
[Method] make_kruskal
크루스칼 알고리즘을 이용하여 최소신장트리를 반환한다.
Graph make_kruskal() {
Graph<T> mst(*this);
Set vertSet;
for(int i = 0; i < vertCnt; i++)
vertSet.add_vert();
MinHeap<Edge<T>> heap;
for(int i = 0; i < edgeCnt; i++) {
heap.push(mst.edgeList[i]);
mst.edgeList[i] = NULL;
}
mst.edgeCnt = 0;
for(Edge<T> *minEdge = heap.pop(); !heap.isEmpty(); minEdge = heap.pop()) {
//if no cycle
if(vertSet.find(minEdge -> vert1 -> key) != vertSet.find(minEdge -> vert2 -> key)) {
vertSet.uni(minEdge -> vert1 -> key, minEdge -> vert2 -> key);
mst.add_edge(minEdge -> vert1, minEdge -> vert2, minEdge -> weight);
}
}
return mst;
}
집합과 최소히프의 개념을 사용하여 시간복잡도를 최소화 시키고자 하였다.
집합 vertSet을 이용하여 O(1)시간 안에 cycle이 생기는지 확인할 수 있다.
그리고 모든 간선들을 최소히프에 넣고 MST에 필요한 간선들만 다시 edgeList에 넣어주는 방식을 선택했다.
간선의 개수가 M개라면 O(log M)시간 안에 최소히프에서 최솟값을 뽑아낼 수 있다.
총 시간 복잡도는 O(M log M)
Source
#include <iostream>
#define VERT_MAX 100
template <typename T>
class Vertex {
public:
T value;
int key;
Vertex(int _key, T _value) : key(_key), value(_value) {};
void print(){
std::cout << "(" << key << ", " << value << ")" << std::endl;
}
bool operator>(const Vertex<T> arg) const {
return this -> key > arg.key;
}
bool operator>(const int arg) const {
return this -> key > arg;
}
bool operator<(const Vertex<T> arg) const {
return this -> key < arg.key;
}
bool operator<(const int arg) const {
return this -> key < arg;
}
bool operator==(const Vertex<T> arg) const {
return this -> key == arg.key;
}
bool operator==(const int arg) const {
return this -> key == arg;
}
};
template <typename T>
class Edge {
public:
Vertex<T> *vert1, *vert2;
int weight;
Edge(Vertex<T> *_vert1, Vertex<T> *_vert2, int _weight) : vert1(_vert1), vert2(_vert2), weight(_weight) {};
bool operator<(const Edge<T> arg) const {
return this -> weight < arg.weight;
}
bool operator>(const Edge<T> arg) const {
return this -> weight > arg.weight;
}
void print(){
std::cout << "(" << vert1 -> key << ", " << vert1 -> value << ")--" << weight << "--(" << vert2 -> key << ", " << vert2 -> value << ")" << std::endl;
}
};
class Set {
public:
int arr[VERT_MAX], vertCnt;
Set(){
for(int i = 0; i < VERT_MAX; i++) arr[i] = -1;
vertCnt = 0;
}
void add_vert() {
arr[vertCnt++] = vertCnt;
}
void uni(int vert1, int vert2) {
if(vert1 < vert2) arr[vert2] = vert1;
else arr[vert1] = vert2;
}
int find(int vert) {
if(arr[vert] == vert) return vert;
else return find(arr[vert]);
}
};
template <typename T>
class MinHeap {
public:
class Node {
public:
T *data;
Node *left, *right;
Node(T *_data) : data(_data), left(NULL), right(NULL) {};
bool operator<(const Node arg) const {
return *(this -> data) < *(arg.data);
}
bool operator>(const Node arg) const {
return *(this -> data) > *(arg.data);
}
};
Node **tree;
int nodeCnt;
MinHeap() {
nodeCnt = 0;
tree = new Node*[VERT_MAX];
}
~MinHeap(){
for(int i = 0; i < nodeCnt; i++) delete tree[i];
delete tree;
}
void swap_node(Node **n1, Node **n2) {
Node *temp = *n1;
*n1 = *n2;
*n2 = temp;
}
void push(T *data) {
tree[++nodeCnt] = new Node(data);
for(int selfIdx = nodeCnt, parentIdx = selfIdx / 2; parentIdx != 0 && *tree[selfIdx] < *tree[parentIdx]; selfIdx /= 2, parentIdx /= 2)
swap_node(&tree[selfIdx], &tree[parentIdx]);
}
T *pop() {
T *returnVal = tree[1] -> data;
swap_node(&tree[1], &tree[nodeCnt]);
tree[nodeCnt--] = NULL;
for(int selfIdx = 1, lIdx = selfIdx * 2, rIdx = selfIdx * 2 + 1;;lIdx = selfIdx * 2, rIdx = selfIdx * 2 + 1) {
if(tree[lIdx] != NULL && tree[rIdx] != NULL) { //if both child have data
if(*tree[selfIdx] < *tree[lIdx] && *tree[selfIdx] < *tree[rIdx]) //if tree is MinHeap
break;
swap_node(&tree[selfIdx], &(*tree[lIdx] < *tree[rIdx] ? tree[lIdx] : tree[rIdx])); //swap itself and smaller child
selfIdx = *tree[lIdx] < *tree[rIdx] ? lIdx : rIdx;
}
else if(tree[lIdx] != NULL) { //if left child has data
if(*tree[selfIdx] < *tree[lIdx])
break;
swap_node(&tree[selfIdx], &tree[lIdx]);
selfIdx = lIdx;
}
else if(tree[rIdx] != NULL) { //if right child has data
if(*tree[selfIdx] < *tree[rIdx])
break;
swap_node(&tree[selfIdx], &tree[rIdx]);
selfIdx = rIdx;
}
else //if no child
break;
}
return returnVal;
}
bool isEmpty() {
return !nodeCnt;
}
void print() {
for(int i = 1; i <= nodeCnt; i++)
tree[i] -> data -> print();
}
};
template <typename T>
class Graph {
public:
Edge<T> **edgeList;
Vertex<T> **vertList;
int edgeCnt, vertCnt;
Graph() {
edgeList = new Edge<T>*[VERT_MAX * VERT_MAX];
vertList = new Vertex<T>*[VERT_MAX];
edgeCnt = vertCnt = 0;
}
Graph(const Graph<T> &origin) : Graph() {
copy(origin);
}
~Graph(){
for(int i = 0; i < edgeCnt; i++) delete edgeList[i];
for(int i = 0; i < vertCnt; i++) delete vertList[i];
delete edgeList;
delete vertList;
}
Graph<T> operator=(const Graph<T>& arg) {
for(int i = 0; i < edgeCnt; i++) delete edgeList[i];
for(int i = 0; i < vertCnt; i++) delete vertList[i];
edgeCnt = vertCnt = 0;
copy(arg);
return *this;
}
void copy(const Graph<T> &origin) {
for(int i = 0; i < origin.vertCnt; i++)
add_vert(origin.vertList[i] -> key, origin.vertList[i] -> value);
for(int i = 0; i < origin.edgeCnt; i++)
add_edge(vertList[origin.edgeList[i] -> vert1 -> key],
vertList[origin.edgeList[i] -> vert2 -> key], origin.edgeList[i] -> weight);
}
void add_vert(int key, T value) {
vertList[vertCnt++] = new Vertex<T>(key, value);
}
void add_edge(Vertex<T> *vert1, Vertex<T> *vert2, int weight) {
edgeList[edgeCnt++] = new Edge<T>(vert1, vert2, weight);
}
void add_edge(int key1, int key2, int weight) {
edgeList[edgeCnt++] = new Edge<T>(vertList[key1], vertList[key2], weight);
}
Graph make_kruskal() {
Graph<T> mst(*this);
Set vertSet;
for(int i = 0; i < vertCnt; i++)
vertSet.add_vert();
MinHeap<Edge<T>> heap;
for(int i = 0; i < edgeCnt; i++) {
heap.push(mst.edgeList[i]);
mst.edgeList[i] = NULL;
}
mst.edgeCnt = 0;
for(Edge<T> *minEdge = heap.pop(); mst.edgeCnt != vertCnt - 1|| !heap.isEmpty(); minEdge = heap.pop()) {
if(vertSet.find(minEdge -> vert1 -> key) != vertSet.find(minEdge -> vert2 -> key)) { //if no cycle
vertSet.uni(minEdge -> vert1 -> key, minEdge -> vert2 -> key);
mst.add_edge(minEdge -> vert1, minEdge -> vert2, minEdge -> weight);
}
}
return mst;
}
};
int main() {
Graph<char> graph, mstGraph;
for(int i = 0; i < 7; i++)
graph.add_vert(i, 'a' + i);
graph.add_edge(0, 1, 28);
graph.add_edge(0, 5, 10);
graph.add_edge(1, 6, 14);
graph.add_edge(1, 2, 16);
graph.add_edge(2, 3, 12);
graph.add_edge(3, 4, 22);
graph.add_edge(3, 6, 18);
graph.add_edge(4, 6, 24);
graph.add_edge(4, 5, 25);
mstGraph = graph.make_kruskal();
for(int i = 0; i < mstGraph.edgeCnt; i++)
(mstGraph.edgeList[i]) -> print();
/*
for(int i = 0; i < g.vertCnt; i++)
(g.vertList[i]) -> print();
for(int i = 0; i < g.edgeCnt; i++)
(g.edgeList[i]) -> print();
MinHeap<Edge<char>> m;
m.push(g.edgeList[0]);
m.push(g.edgeList[1]);
m.push(g.edgeList[2]);
m.push(g.edgeList[3]);
m.push(g.edgeList[4]);
m.print();
std::cout<<"pop: ";
m.pop() -> print();
m.print();
*/
}
좋아요공감
공유하기
통계
글 요소
'Study > Data Structure' 카테고리의 다른 글
| Dijkstra 다익스트라 (C++) (0) | 2020.11.16 |
|---|---|
| DFS / BFS 그래프 탐색 (C++) (0) | 2020.11.14 |
| Loser Tree 패자트리 (C++) (0) | 2020.11.01 |
| Binary Search Tree 이진 탐색 트리 (C++) (0) | 2020.11.01 |
| MaxHeap (0) | 2020.11.01 |
Comment