企业官网建设流程全解析

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++实现:

#include<iostream>#include<vector>#include<algorithm>#include<set>usingnamespacestd;structEdgeNode{size_t vertex_id;EdgeNode*next=nullptr;EdgeNode(size_t&v):vertex_id(v){}};template<typenameT>structEdgeInfo{longlongu;longlongv;T weight;booloperator<(constEdgeInfo&e){returnweight<e.weight;}booloperator>(constEdgeInfo&e){returne.weight<weight;}booloperator==(constEdgeInfo&e){return!(weight<e.weight)&&!(e.weight<weight);}booloperator<=(constEdgeInfo&e){return!(e.weight<weight);}booloperator>=(constEdgeInfo&e){return!(weight<e.weight);}EdgeInfo()=default;EdgeInfo(longlong_u,longlong_v,constT&_weight):u(_u),v(_v),weight(_weight){}};classGraph{public:Graph(constsize_t&N):vertex_list(N,nullptr){};boolinsertEdge(size_t u,size_t v){if(u!=v&&u<vertex_list.size()&&v<vertex_list.size()){if(vertex_list[u]==nullptr){vertex_list[u]=newEdgeNode(v);}else{EdgeNode*t=newEdgeNode(v);t->next=vertex_list[u];vertex_list[u]=t;}if(vertex_list[v]==nullptr){vertex_list[v]=newEdgeNode(u);}else{EdgeNode*t=newEdgeNode(u);t->next=vertex_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(cur==nullptr)returnnullptr;returncur->next;}private:vector<EdgeNode*>vertex_list;};voidedgeNumAndWeightSum(Graph&g,size_t&EdgeNum,int&WeightSum,vector<vector<pair<bool,int>>>&_edge){EdgeNum=0;WeightSum=0;for(size_t i=0;i<g.getVertexNum();++i){for(EdgeNode*run=g.getFirstEdge(i);run!=nullptr;run=g.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){longlongp=n;while(_set[p]>=0){p=_set[p];}longlongcur=n;while(cur!=p){longlongtemp=_set[cur];_set[cur]=p;cur=temp;}returnp;}voidunionSet(longlongleft,longlongright){longlongleft_set=findSet(left);longlongright_set=findSet(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:vector<longlong>_set;};template<typenameT>classHeap{public:Heap()=default;Heap(constvector<T>&input){heap=input;for(size_t run=heap.size()/2;run>=1;--run){updownAdjust(run-1);}}voidinsert(constT&key);boolremoveMinValue(T&key);void_clear(){heap.clear();}private:voidupdownAdjust(size_t top);voiddownupAdjust();vector<T>heap;};template<typenameT>boolHeap<T>::removeMinValue(T&key){if(heap.empty())returnfalse;key=heap[0];swap(heap[0],heap.back());if(heap.size()>=2)heap.pop_back();updownAdjust(0);returntrue;}template<typenameT>voidHeap<T>::insert(constT&key){heap.push_back(key);downupAdjust();}template<typenameT>voidHeap<T>::updownAdjust(size_t top){size_t cur=top+1;size_t temp=2*cur;T value=heap[top];while(temp<=heap.size()){if(temp<heap.size()&&heap[temp-1]>heap[temp]){++temp;}if(heap[temp-1]>=value){break;}heap[cur-1]=heap[temp-1];cur=temp;temp*=2;}heap[cur-1]=value;}template<typenameT>voidHeap<T>::downupAdjust(){size_t cur=heap.size();size_t temp=cur/2;T value=heap.back();while(cur>1){if(heap[temp-1]<=value){break;}heap[cur-1]=heap[temp-1];cur=temp;temp/=2;}heap[cur-1]=value;}#defineN6intmain(){vector<EdgeInfo<int>>input{EdgeInfo<int>(0,1,6),EdgeInfo<int>(0,2,1),EdgeInfo<int>(0,3,5),EdgeInfo<int>(1,2,5),EdgeInfo<int>(1,4,3),EdgeInfo<int>(2,4,6),EdgeInfo<int>(2,3,5),EdgeInfo<int>(2,5,4),EdgeInfo<int>(3,5,2),EdgeInfo<int>(4,5,6)};vector<vector<pair<bool,int>>>EdgeWeightInfo(N,vector<pair<bool,int>>(N,make_pair(false,-1)));for(constauto&run:input){EdgeWeightInfo[run.u][run.v]=make_pair(true,run.weight);EdgeWeightInfo[run.v][run.u]=make_pair(true,run.weight);}Heap<EdgeInfo<int>>h(input);UnionFindSet_set(N);Graphg(N);for(size_t i=1;i<N;++i){while(true){EdgeInfo<int>temp;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();vector<vector<pair<bool,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}}};vector<bool>in_S_or_in_T{true,false,false,false,false,false};Graph_graph(N);for(size_t j=0;j<_edge[0].size();++j){if(_edge[0][j].first){h.insert(EdgeInfo<int>(0,j+1,_edge[0][j].second));}}for(size_t i=1;i<N;++i){while(true){EdgeInfo<int>temp;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 p=0;p!=in_S_or_in_T.size();++p){if(in_S_or_in_T[p]==false){if(temp.u<p){if(_edge[temp.u][p-temp.u-1].first){h.insert(EdgeInfo<int>(temp.u,p,_edge[temp.u][p-temp.u-1].second));}}else{if(_edge[p][temp.u-p-1].first){h.insert(EdgeInfo<int>(p,temp.u,_edge[p][temp.u-p-1].second));}}}}break;}}}size_t EdgeNum;intWeightSum;edgeNumAndWeightSum(_graph,EdgeNum,WeightSum,EdgeWeightInfo);cout<<"Prim算法边数"<<EdgeNum<<"权重和"<<WeightSum<<endl;edgeNumAndWeightSum(g,EdgeNum,WeightSum,EdgeWeightInfo);cout<<"Kruskal算法边数"<<EdgeNum<<"权重和"<<WeightSum<<endl;return0;}