普裡姆算法 Prim

原先一直沒注意這個算法，一直以為迪傑斯特拉可以解決相關問題。後來發現迪傑斯特拉必須要有起點，否則就gg了。而這也是迪傑斯特拉和普裡姆的最大差別。

算法簡述

普裡姆算法的本質是貪心。

常見疑惑的說明：

1.是否可能需要再次更新？

由于已經使用每一個确定最短路長度的節點更新過目前節點，故無需再次更新（因為一個點不能多次到達）。

2.為何把距離起點最近的點作為新的确定最短路長度的節點？

由于該節點是所有尚未确定距離節點中距離起點最短的點，不可能被其它尚未确定距離的節點更新。是以該節點可以作為新的确定最短路長度的節點。

代碼實作

class Prim{
public:
    int prim(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>> routes(n+1);
        int ans=0,cnt=0;
        for(const auto& edge:edges)
        {
            routes[edge[0]].push_back(make_pair(edge[1],edge[2]));
            routes[edge[1]].push_back(make_pair(edge[0],edge[2]));
        }
        vector<int> used(n+1);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;//pq stores {distance,target}

        pq.emplace(0,1);//choose a starting point
        while(!pq.empty()&&cnt<n)
        {
            auto node=pq.top();
            pq.pop();
            int dis=node.first,x=node.second; 
            if(!used[x])
            {
                ans+=dis;
                used[x]=1;
                cnt++;
                for(const auto &route:routes[x])//traverse the edge starting from vertex x
                    pq.emplace(route.second,route.first);
            } 
        }

        if(cnt<n)
            return -1;
        return ans;
    }
};
           

時間複雜度	空間複雜度	補充說明	适用範圍
采用堆	\(O(n+eloge)\)	\(O(n+e)\)	無	頂點數大于邊數（稀疏圖）