테스트 테스트

ㅇ나아아아

ㅔㅌ스트

컬러 스크립터 써보는 중

#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()
    {
        cout << "Kruskal : \n";
        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);
            }
        }
    }
 
 
    int getMinVtxIdx(bool selected[], int dist[])
    {
        int minVertexIndex = 0;
        int mindist = INF;
        for (int i = 0; i< size; ++i)
        {
            if (!selected[i] && dist[i] < mindist)
            {
                mindist = dist[i];
                minVertexIndex = i;
            }
        }
        return minVertexIndex;
 
    }
 
    void Prim(int s)
    {
        cout << "Prim : \n";
        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)
        {
            int index = getMinVtxIdx(selected, dist);
            selected[index] = true;
            if (dist[index] == INF) return;
 
            cout << getVertexName(index) << " ";
 
            for (int i = 0; i < size; ++i)
                if (getEdge(index, i) != INF)
                    if (!selected[i] && getEdge(index, i) < dist[i])
                        dist[i] = getEdge(index, i);
 
        }
        cout << endl;
    }
 
};