구현 - 가중치 그래프와 크루스칼 알고리즘

인접행렬 그래프를 상속한 가중치 그래프의 모습

 

WGraph.h

#pragma once

#include "AdjMatGraph.h"

#define INF 9999

class WGraph : public AdjMatGraph

{

public:

void reset()

{

size = 0;

for (int i = 0; i < MAX_VTXS; ++i)

for (int j = 0; j < MAX_VTXS; ++j)

setEdge(i, j, INF);

}

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(istream& fin)

{

if (!fin) return;

int size;

fin >> size;

for (int i = 0; i < size; ++i)

{

char vName;

fin >> vName;

insertVertex(vName);

for (int j = 0; j < size; ++j)

{

int val;

fin >> val;

insertEdge(i, j, val);

}

}

}

};

가중치 그래프를 상속한 MST (minimum spanning tree)

책이랑 로직은 같은데 표현방식이 많이 다르다. std::tuple과 std::priority_queue를 사용했다.

WGraphMST.h

#include <queue>

#include "WGraph.h"

#include "VertexSets.h"

#include <functional>

using namespace std;

using vertex = std::tuple<int, int, int>;

class WGraphMST : public WGraph

{

public:

void Kruskal()

{

priority_queue<vertex, vector<vertex>, greater<vertex>> q;

for (int i = 0; i < size - 1; ++i)

{

for (int j = i + 1; j < size; ++j)

{

if (hasEdge(i, j))

q.push(make_tuple(getEdge(i, j), i, j));

}

}

VertexSets set(size);

while (!set.isOne())

{

auto e = q.top();

q.pop();

int uset = set.findSet(get<1>(e));

int vset = set.findSet(get<2>(e));

if (uset != vset)

{

cout << "간선 추가 : " << getVertexName(get<1>(e)) << " - "

<< getVertexName(get<2>(e)) << " 비용 : " << get<0>(e) << endl;

set.unionSets(uset, vset);

}

}

}

};

이부분은 책 내용 거의 그대로.. 처음에 이해가 안되서 한참 봤다.

정점 i, j가 같은 집합에 속해있는지 알아 낼 때 findSet을 사용하며 집합을 합치는 기능이 있다.

정점 크기만큼의 개수가 있는 집합들이 unionSet으로 합칠 때마다 하나씩 줄어든다. 가령 unisionSet(1, 2)는 1을 2의 종속으로 만드는 느낌이다.

#pragma once

#ifndef MAX_VTXS

#define MAX_VTXS 256

#endif

class VertexSets

{

int _parent[MAX_VTXS];

int _size;

public:

VertexSets(int size) : _size(size)

{

for (int i = 0; i < size; ++i)

_parent[i] = -1;

}

bool isRoot(int vIndex) { return _parent[vIndex] < 0; }

int findSet(int vIndex)

{

while (!isRoot(vIndex)) vIndex = _parent[vIndex];

return vIndex;

}

void unionSets(int s1, int s2)

{

_parent[s1] = s2;

_size--;

}

bool isOne() { return _size == 1; }

};

main.cpp

#include "WGraphMST.h"

int main()

{

WGraphMST g;

g.load(ifstream("grap.txt"));

g.display();

cout << endl;

g.Kruskal();

}

덧 : 혹시나 필요할 수 도있으니 AdjMatGraph.h

#pragma once
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define MAX_VTXS 256
 
class AdjMatGraph
{
protected:
    int size;
    char vertexName[MAX_VTXS];
    int edges[MAX_VTXS][MAX_VTXS];
 
public:
    AdjMatGraph() { reset(); }
    char getVertexName(int i) { return vertexName[i]; }
    int getEdge(int i, int j) { return edges[i][j]; }
    void setEdge(int i, int j, int val) { edges[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()) vertexName[size++] = name;
        else cout << "Error : full\n";
    }
    void insertEdge(int u, int v)
    {
        setEdge(u, v, 1);
        setEdge(v, u, 1);
    }
    void display(ostream& out = cout)
    {
        out << size << endl;
        for (int i = 0; i < size; i++)
        {
            out << vertexName[i] << "  ";
            for (int j = 0; j < size; ++j)
                out << setw(5) << getEdge(i, j);
            out << endl;
        }
    }
};