P算法

prim 算法

prim 算法

#include "graph.hpp"

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

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

// Minimum Spanning Tree
unordered_set<Edge *> primMST(Graph *graph)
{
    // 解锁的边进入小根堆
    priority_queue<Edge *, vector<Edge *>, cmpEdge> pq;
    unordered_set<Node *> myset;
    unordered_set<Edge *> result;

    // 随便选择一个 Node 作为起点去解锁边
    // 这里本来随便选一个 node 去处理即可，这里加上for循环遍历所有 node 仅仅是为了
    // 处理森林的问题，因为可能会存在一个图有多个连通区域的情况
    for (auto &it : graph->nodes)
    {
        // 当前点不在 myset 点集合
        if (myset.find(it.second.get()) == myset.end())
        {
            myset.insert(it.second.get());
            // 解锁跟这条边相连的所有边
            for (auto &edge : it.second.get()->edges)
            {
                // 小根堆加入重复值会怎样
                pq.push(edge);
            }
            while (!pq.empty())
            {
                // 弹出解锁的边中权值最小的边
                Edge *edge = pq.top();
                pq.pop();
                // 判断这个边的 toNode 是否在大集合里
                Node *toNode = edge->to;
                // 不含有当前点则说明是新的点
                if (myset.find(toNode) == myset.end())
                {
                    result.insert(edge);
                    // 边会重复进入这个队列，即便重复的边被压入队列，但是由于toNode在大集合里面
                    // 所有会直接跳过
                    for (auto &nextEdge : toNode->edges)
                    {
                        pq.push(nextEdge);
                    }
                }
            }
        }
    }
    return result;
}

void test1()
{
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(1);
    pq.push(1);
    pq.push(1);
    pq.push(1);
    while (!pq.empty())
    {
        cout << pq.top() << endl;
        pq.pop();
    }
}

int main()
{
    test1();

    return 0;
}