《数据结构》第13章最小生成树.ppt

*第13章最小生成树生成树与最小生成树Kruskal算法Prim算法算法的正确性*生成树ABCDEHMABCDEHM无向图G无向图G的生成树生成树是无向连通图的极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添加一条边之后,必定会形成回路或环。*最小生成树定义:加权无向图的所有生成树中边的权值(代价)之和最小的树。实例:1243566165556342**********左图的最小代价生成树*Kruscal算法基本思想:考虑图中权值最小的边。如果加入这条边不会导致回路,则加入;否则考虑下一条边,直到包含了所有的顶点实现:初始时,设置生成树为(V,Φ),如果V有n个顶点,则初始的生成树为具有n个连通分量的树。按权值的大小逐个考虑所有的边,如果改变的加入能连接两个连通分量,则加入。当生成树只有一个连通分量时,算法结束。*12435661655563421、初始连通分量:{1},{2},{3},{4},{5},{6}2、反复执行添加、放弃动作。边 动作 连通分量(1,3)添加 {1,3},{4},{5},{6},{2}(4,6)添加 {1,3},{4,6},{2},{5}(2,5)添加 {1,3},{4,6},{2,5}(3,6)添加 {1,3,4,6},{2,5}(1,4)放弃 因构成回路(3,4)放弃 因构成回路(2,3)添加 {1,3,4,5,6,2}最小代价生成树***********算法难点及解决方案如何从所有边中选择代价最小的边:用一个优先级队列来实现。将所有的边放入一个优先级队列,边的优先级就是它的权值。权值越小,优先级越高。如何判断加入一条边后会不会形成回路:用并查集来实现。将一个连通分量表示为并查集中的一个子集,检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行Find操作。如果两个Find的结果相同,则表示两个端点已连通,加入这条边会形成回路,否则将这条边加入生成树。添加边的操作就是一个Union操作,将两个端点所属的子集归并起来,表示其中的所有顶点都已连通。*定义优先级队列中的元素类型structedge{intbeg,end;TypeOfEdgew;booloperator<(constedge&rp)const{returnw<;}};*kruskal算法的实现template<classTypeOfVer,classTypeOfEdge>voidadjListGraph<TypeOfVer,TypeOfEdge>::kruskal()const{epted=0,u,v;edgeNode*p;edgee;DisjointSetds(Vers);priorityQueue<edge>pq;//生成优先级队列for(inti=0;i<Vers;++i){ for(p=verList[i].head;p!=NULL;p=p->next) if(i<p->end){=i; =p->end; =p->weight; (e);} }*//开始归并while(epted<Vers-1){e=();u=(); v=();if(u!=v){epted++;(u,v); cout<<'('<<verList[].ver<<','<<verList[].ver<<")\t";}}}