Kruskal算法执行流程:初始化:图的每一个顶点各自在只有自己组成的连通分量里执行过程:按从小到大的顺序遍历图的所有边,对于当前边e如果e的两个端点在同一个连通分量里忽略e否则合并e的两个端点各自所在的连通分量为一个连通分量,并把e加入最小生成树的边集合.当处理的未被忽略的边e的数量达到图的顶点数减1算法终止Prim算法的执行流程;初始化:选择一个顶点v0,把所有顶点划分为两个集合S和T,v0在S中,剩余顶点在T中,把一端为v0另一端在T中所有边加入集合E执行过程:从E中选择一条权值最小的跨越S,T的边e,将e加入最小生成树,将e在T中的端点v从T中移出放入S,并将所有一端为s另一端在T中的所有边加入E,然后重复迭代,当T为空集时终止算法Kruskal算法的正确性证明:截取自王树禾图论第二版2.4节定理2.4的证明Prim算法正确性证明:截取自算法导论第三版23.1节C实现:#includeiostream#includevector#includealgorithm#includesetusingnamespacestd;structEdgeNode{size_t vertex_id;EdgeNode*nextnullptr;EdgeNode(size_tv):vertex_id(v){}};templatetypenameTstructEdgeInfo{longlongu;longlongv;T weight;booloperator(constEdgeInfoe){returnweighte.weight;}booloperator(constEdgeInfoe){returne.weightweight;}booloperator(constEdgeInfoe){return!(weighte.weight)!(e.weightweight);}booloperator(constEdgeInfoe){return!(e.weightweight);}booloperator(constEdgeInfoe){return!(weighte.weight);}EdgeInfo()default;EdgeInfo(longlong_u,longlong_v,constT_weight):u(_u),v(_v),weight(_weight){}};classGraph{public:Graph(constsize_tN):vertex_list(N,nullptr){};boolinsertEdge(size_t u,size_t v){if(u!vuvertex_list.size()vvertex_list.size()){if(vertex_list[u]nullptr){vertex_list[u]newEdgeNode(v);}else{EdgeNode*tnewEdgeNode(v);t-nextvertex_list[u];vertex_list[u]t;}if(vertex_list[v]nullptr){vertex_list[v]newEdgeNode(u);}else{EdgeNode*tnewEdgeNode(u);t-nextvertex_list[v];vertex_list[v]t;}returntrue;}returnfalse;}size_tgetVertexNum(){returnvertex_list.size();}EdgeNode*getFirstEdge(size_t u){returnvertex_list[u];}EdgeNode*nextEdge(EdgeNode*cur){if(curnullptr)returnnullptr;returncur-next;}private:vectorEdgeNode*vertex_list;};voidedgeNumAndWeightSum(Graphg,size_tEdgeNum,intWeightSum,vectorvectorpairbool,int_edge){EdgeNum0;WeightSum0;for(size_t i0;ig.getVertexNum();i){for(EdgeNode*rung.getFirstEdge(i);run!nullptr;rung.nextEdge(run)){EdgeNum;WeightSum_edge[i][run-vertex_id].second;}}EdgeNum/2;WeightSum/2;}classUnionFindSet{public:UnionFindSet(size_t N):_set(N,-1){}longlongfindSet(longlongn){longlongpn;while(_set[p]0){p_set[p];}longlongcurn;while(cur!p){longlongtemp_set[cur];_set[cur]p;curtemp;}returnp;}voidunionSet(longlongleft,longlongright){longlongleft_setfindSet(left);longlongright_setfindSet(right);if(left_set!right_set){if(_set[left_set]_set[right_set]){_set[left_set]_set[right_set];_set[right_set]left_set;}else{_set[right_set]_set[left_set];_set[left_set]right_set;}}}private:vectorlonglong_set;};templatetypenameTclassHeap{public:Heap()default;Heap(constvectorTinput){heapinput;for(size_t runheap.size()/2;run1;--run){updownAdjust(run-1);}}voidinsert(constTkey);boolremoveMinValue(Tkey);void_clear(){heap.clear();}private:voidupdownAdjust(size_t top);voiddownupAdjust();vectorTheap;};templatetypenameTboolHeapT::removeMinValue(Tkey){if(heap.empty())returnfalse;keyheap[0];swap(heap[0],heap.back());if(heap.size()2)heap.pop_back();updownAdjust(0);returntrue;}templatetypenameTvoidHeapT::insert(constTkey){heap.push_back(key);downupAdjust();}templatetypenameTvoidHeapT::updownAdjust(size_t top){size_t curtop1;size_t temp2*cur;T valueheap[top];while(tempheap.size()){if(tempheap.size()heap[temp-1]heap[temp]){temp;}if(heap[temp-1]value){break;}heap[cur-1]heap[temp-1];curtemp;temp*2;}heap[cur-1]value;}templatetypenameTvoidHeapT::downupAdjust(){size_t curheap.size();size_t tempcur/2;T valueheap.back();while(cur1){if(heap[temp-1]value){break;}heap[cur-1]heap[temp-1];curtemp;temp/2;}heap[cur-1]value;}#defineN6intmain(){vectorEdgeInfointinput{EdgeInfoint(0,1,6),EdgeInfoint(0,2,1),EdgeInfoint(0,3,5),EdgeInfoint(1,2,5),EdgeInfoint(1,4,3),EdgeInfoint(2,4,6),EdgeInfoint(2,3,5),EdgeInfoint(2,5,4),EdgeInfoint(3,5,2),EdgeInfoint(4,5,6)};vectorvectorpairbool,intEdgeWeightInfo(N,vectorpairbool,int(N,make_pair(false,-1)));for(constautorun:input){EdgeWeightInfo[run.u][run.v]make_pair(true,run.weight);EdgeWeightInfo[run.v][run.u]make_pair(true,run.weight);}HeapEdgeInfointh(input);UnionFindSet_set(N);Graphg(N);for(size_t i1;iN;i){while(true){EdgeInfointtemp;h.removeMinValue(temp);longlongleft_set.findSet(temp.u);longlongright_set.findSet(temp.v);if(left!right){g.insertEdge(temp.u,temp.v);_set.unionSet(left,right);break;}}}h._clear();vectorvectorpairbool,int_edge{{{true,6},{true,1},{true,5},{false,-1},{false,-1}},{{true,5},{false,-1},{true,3},{false,-1}},{{true,5},{true,6},{true,4}},{{false,-1},{true,2}},{{true,6}}};vectorboolin_S_or_in_T{true,false,false,false,false,false};Graph_graph(N);for(size_t j0;j_edge[0].size();j){if(_edge[0][j].first){h.insert(EdgeInfoint(0,j1,_edge[0][j].second));}}for(size_t i1;iN;i){while(true){EdgeInfointtemp;h.removeMinValue(temp);if(in_S_or_in_T[temp.u]false||in_S_or_in_T[temp.v]false){if(in_S_or_in_T[temp.u])swap(temp.u,temp.v);in_S_or_in_T[temp.u]true;_graph.insertEdge(temp.u,temp.v);for(size_t p0;p!in_S_or_in_T.size();p){if(in_S_or_in_T[p]false){if(temp.up){if(_edge[temp.u][p-temp.u-1].first){h.insert(EdgeInfoint(temp.u,p,_edge[temp.u][p-temp.u-1].second));}}else{if(_edge[p][temp.u-p-1].first){h.insert(EdgeInfoint(p,temp.u,_edge[p][temp.u-p-1].second));}}}}break;}}}size_t EdgeNum;intWeightSum;edgeNumAndWeightSum(_graph,EdgeNum,WeightSum,EdgeWeightInfo);coutPrim算法边数EdgeNum权重和WeightSumendl;edgeNumAndWeightSum(g,EdgeNum,WeightSum,EdgeWeightInfo);coutKruskal算法边数EdgeNum权重和WeightSumendl;return0;}