模板下载网站源码 模板下载网站织梦模板,网站建设公司浩森宇特,襄樊网站建设哪家好,租服务器的网站prim和dijkstra每轮找最小边的松弛操作其实是同源的#xff0c;因而受dijkstra堆优化的启发#xff0c;那么prim也可以采用小根堆进行优化。时间复杂度也由 O ( n 2 ) O(n^2) O(n2)降为 O ( n l o g n ) O(nlogn) O(nlogn)。 测试一下吧#xff1a;原题链接
#include i…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 pairint,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_queuePII, vectorPII, greaterPII 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;
}
