- prim和dijkstra每轮找最小边的松弛操作其实是同源的,因而受dijkstra堆优化的启发,那么prim也可以采用小根堆进行优化。
- 时间复杂度也由 O ( n 2 ) O(n^2) O(n2)降为 O ( n l o g n ) O(nlogn) O(nlogn)。
测试一下吧:原题链接
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef int VertexType;
typedef int Info;
typedef pair<int,int> PII;const int N = 110;// 书面形式的邻接表
typedef struct ArcNode{int adjvex;Info weight;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode{VertexType data; // 这里 结点编号就是结点表的下标 一一映射ArcNode* firstarc;
}VNode, AdjList[N];
typedef struct ALGraph{AdjList vertices;int vexnum, arcnum;ALGraph(){for(int i = 0;i < N;i ++) vertices[i].firstarc = nullptr;}
}ALGraph;int prim_with_heap(ALGraph& G){int sum = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;int dist[N];bool st[N];memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[1] = 0;heap.push({0, 1});while(heap.size()){PII t = heap.top();heap.pop();int vex = t.second, distance = t.first;if(st[vex]) continue;st[vex] = true;sum += distance;for(ArcNode* parc = G.vertices[vex].firstarc;parc;parc = parc -> nextarc)if((parc -> weight) < dist[parc -> adjvex]){dist[parc -> adjvex] = parc -> weight;heap.push({parc -> weight, parc -> adjvex});}}return sum;
}void add(ALGraph& G, VertexType a, VertexType b, Info w){ // a -> bVNode* u = &G.vertices[a];ArcNode* newarc = new ArcNode;newarc -> adjvex = b;newarc -> weight = w;newarc -> nextarc = u -> firstarc;u -> firstarc = newarc; // 头插法G.arcnum ++;
}int main(){ALGraph g;cin >> g.vexnum;for(int i = 1;i <= g.vexnum;i ++)for(int j = 1;j <= g.vexnum;j ++){int w;cin >> w;add(g, i, j, w);}int sum = prim_with_heap(g);cout << sum << endl;return 0;
}