K算法

Kruskal 算法

Kruskal 算法

#include "graph.hpp"

#include <list>
#include <stdlib.h>
#include <crtdbg.h>
using namespace std;

/*
K 算法实现
*/

// 简单的并查集的实现
// 并查集的功能：1、查询(O(1)时间复杂度)；2、合并(O(1)时间复杂度)
class mySets
{
public:
    // value 必须申请在堆上，list 类型指针也必须有唯一性，否则后面查讯集合是否为同一个集合复杂度会比较高
    // 对于一般的算法机考题：Node*可以用int代替，对于list<Node*>*可以定义一个list<Node*>* arr[nodeSize]的数组
    // 然后value部分也用int表示
    unordered_map<Node *, list<Node *> *> setMap;
    // just for delete
    vector<list<Node *> *> newArr;

    mySets(list<Node *> nodes)
    {
        for (auto &cur : nodes)
        {
            list<Node *> *set = new list<Node *>();
            newArr.push_back(set);
            set->emplace_back(cur);
            setMap.emplace(cur, set);
        }
    }

    // 查询是否为同一个集合
    bool isSameSet(Node *from, Node *to)
    {
        if (setMap.find(from) == setMap.end() || setMap.find(to) == setMap.end())
        {
            return false;
        }

        list<Node *> *fromSet = setMap[from];
        list<Node *> *toSet = setMap[to];
        return fromSet == toSet;
    }

    // 合并集合，这里时间复杂度是O(N)
    void unionSet(Node *from, Node *to)
    {
        if (setMap.find(from) == setMap.end() || setMap.find(to) == setMap.end())
        {
            return;
        }

        list<Node *> *fromSet = setMap[from];
        list<Node *> *toSet = setMap[to];
        // 将 toSet 集合中所有的节点全部由fromSet负责
        for (auto &toNode : *toSet)
        {
            fromSet->emplace_back(toNode);
            setMap[toNode] = fromSet;
        }

        // 在这里 delete toSet 或者再创建一个用于delete回收的数组
    }

    // 析构函数释放申请的 list 类型指针
    ~mySets()
    {
        for (auto &it : newArr)
        {
            delete it;
        }
    }
};

class cmpEdge
{
public:
    bool operator()(const Edge *e1, const Edge *e2) const
    {
        return e1->weight > e2->weight;
    }
};

unordered_set<Edge *> kruskalMST(Graph *graph)
{
    list<Node *> nodes;
    for (auto &it : graph->nodes)
    {
        nodes.emplace_back(it.second.get());
    }
    mySets myset(nodes);
    // 以 Edge 的 weight 属性来构建小根堆
    priority_queue<Edge *, vector<Edge *>, cmpEdge> pq;
    // M 条边 O(logM)
    for (auto &edge : graph->edges)
    {
        pq.push(edge.get());
    }

    unordered_set<Edge *> res;
    // M 条边 O(logM)
    while (!pq.empty())
    {
        Edge *edge = pq.top();
        pq.pop();
        // O(1)
        if (!myset.isSameSet(edge->from, edge->to))
        {
            res.insert(edge);
            // 这里用真正的并查集可以做到 O(1)
            myset.unionSet(edge->from, edge->to);
        }
    }
    return res;
}

void test1()
{
    Node n1(1);
    Node n2(2);
    Node n3(3);
    list<Node *> nodes = {&n1, &n2, &n3};
    mySets set(nodes);
    for (auto &it : *(set.setMap[&n2]))
    {
        cout << it->value << endl;
    }
    // _CrtDumpMemoryLeaks();	//检测内存泄露
}

void test2()
{
    vector<vector<int>> matrix = {{2, 1, 3}, {7, 1, 2}, {100, 1, 4}, {4, 3, 4}, {1000, 2, 4}, {100000, 2, 5}};
    shared_ptr<Graph> graph = creatGraph(matrix);
    unordered_set<Edge *> res = kruskalMST(graph.get());
    for(auto & it : res)
    {
        cout << "weight: " << it->weight << "; " << "from: " << it->from->value << "; " << "to: " << it->to->value << endl;
    }
}

int main()
{
    test2();

    _CrtDumpMemoryLeaks(); // 检测内存泄露

    return 0;
}