《最小生成树ppt课件》由会员分享，可在线阅读，更多相关《最小生成树ppt课件（20页珍藏版）》请在金锄头文库上搜索。
1、最小生成树最小生成树最小生成树 ( minimum cost spanning tree )使用不同的遍历图的方法，可以得到不同的生使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的生成树。生成树。按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1 条边。条边。构造最小生成树的准则构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用 n- -1 条边来联结网络中的条边来联结网络
2、中的 n 个个顶点；顶点；不能使用产生回路的边。不能使用产生回路的边。克鲁斯卡尔克鲁斯卡尔 ( (KruskalKruskal) ) 算法算法克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想： 设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N = V, E ,最初先构造一个只有最初先构造一个只有 n 个顶点，没有边的非个顶点，没有边的非连通图连通图 T = V, , 图中每个顶点自成一个连图中每个顶点自成一个连通分量。当在通分量。当在 E 中选到一条具有最小权值的边中选到一条具有最小权值的边时时,若该边的两个顶点落在不同的连通分量上，若该边的两个顶点落在不同的连通分量上，则将此
3、边加入到则将此边加入到 T 中；否则将此边舍去，重新中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。所有顶点在同一个连通分量上为止。算法的框架算法的框架我们利用最小堆我们利用最小堆(MinHeap)和并查和并查集集(DisjointSets)来实现克鲁斯卡尔算法。来实现克鲁斯卡尔算法。首先，利用最小堆来存放首先，利用最小堆来存放E中的所有的边中的所有的边, 堆堆中每个结点的格式为中每个结点的格式为在构造最小生成树的过程中，最小堆中存放剩在构造最小生成树的过程中，最小堆中存放剩余的边，并且利用并查集的运算检查
4、依附于一余的边，并且利用并查集的运算检查依附于一条边的两个顶点条边的两个顶点 tail、head 是否在同一个连通是否在同一个连通分量分量 (即并查集的同一个子集合即并查集的同一个子集合) 上上, 是则舍是则舍去这条边；否则将此边加入去这条边；否则将此边加入 T，同时将这两个同时将这两个顶点放在同一个连通分量上。随着各边逐步加顶点放在同一个连通分量上。随着各边逐步加入到最小生成树的边集合中，各连通分量也在入到最小生成树的边集合中，各连通分量也在逐步合并，直到形成一个连通分量为止。逐步合并，直到形成一个连通分量为止。 tail head cost 边的两个顶点位置边的两个顶点位置 边的权值边的权
5、值应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程最小生成树类定义最小生成树类定义const int MAXINT = 机器可表示的机器可表示的, 问题中不可问题中不可 能出现的大数能出现的大数class MinSpanTree;class MSTEdgeNode /生成树边结点类生成树边结点类定义定义friend class MinSpanTree;private: int tail, head; /生成树各边的两顶点生成树各边的两顶点 float cost; /生成树各边的代价生成树各边的代价;class MinSpanTree /生成树的类定义生成树的类定义p
6、ublic: MinSpanTree ( int sz = NumVertices -1 ) : MaxSize (sz), n (0) edgevalue = new MSTEdgeNodeMaxSize; int Insert ( MSTEdgeNode & item ); /将将item加到最小生成树中加到最小生成树中protected: MSTEdgeNode *edgevalue; /边值数组边值数组 int MaxSize, n; /最大边数最大边数,当前边数当前边数;利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树void Graph :Kruskal ( Min
7、SpanTree& T ) MSTEdgeNode e; /边结点辅助单元边结点辅助单元 MinHeap H(CurrentEdges); int NumVertices = VerticesList.last; /顶点个顶点个数数 UFSets F (NumVertices); /并查集并查集F 并初始并初始化化 for ( int u = 0; u NumVertices; u+ ) /邻接矩邻接矩阵阵 for ( int v = u +1; v NumVertices; v+ ) if ( Edgeuv != MAXNUM ) /所有边所有边 e.tail = u; e.head = v
8、; e.cost = Edgeuv; H.Insert (e); /插入插入堆堆 int count = 1; /最小生成树加入边数的计数最小生成树加入边数的计数 while ( count NumVertices ) H.RemoveMin ( e ); /从堆中退出一条边从堆中退出一条边 u = F.Find ( e.tail ); /检测两端点的根检测两端点的根v = F.Find ( e.head );if ( u != v ) /根不同不在同一连通分量根不同不在同一连通分量 F.Union ( u, v ); /合并合并 T.Insert ( e ); /该边存入最小生成树该边存入最
9、小生成树 T count+; 出堆顺序出堆顺序 (0,5,10) 选中选中 (2,3,12) 选中选中 (1,6,14) 选中选中 (1,2,16) 选中选中 (3,6,18) 舍弃舍弃 (3,4,22) 选中选中 (4,6,24) 舍弃舍弃 (4,5,25) 选中选中并查集邻接矩阵表示-2-2-2-2-1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1-102-1-1-10-2200000 1 2 3 4 5 6-21-11-2-1-421-2 -51211-711211F 0 1 2 3 4 5 6 0 28 10 028 0 16 14 1 16 0 12 2 12 0 22
10、18 3 22 0 25 24 410 25 0 5 14 18 24 0 6在建立最小堆时需要检测邻接矩阵，计算的在建立最小堆时需要检测邻接矩阵，计算的时间代价为时间代价为 O(n2)。且做了且做了 e 次堆插入操作次堆插入操作, 每次插入调用了一个堆调整算法每次插入调用了一个堆调整算法FilterUp( )算算法法, 因此堆插入需要的时间代价为因此堆插入需要的时间代价为 O(elog2e)。在构造最小生成树时，最多调用了在构造最小生成树时，最多调用了 e 次出堆次出堆操作操作RemoveMin( )，2e 次并查集的次并查集的Find( )操操作，作，n-1次次Union( )操作，计算时
11、间分别为操作，计算时间分别为 O(elog2e)，O(elog2n)和和O(n)。总的计算时间为总的计算时间为 O(elog2e + elog2n + n2 + n )普里姆普里姆(Prim)(Prim)算法算法普里姆算法的基本思想：普里姆算法的基本思想： 从连通网络从连通网络 N = V, E 中的某一顶点中的某一顶点 u0 出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合U中。中。 以后每一步从以后每一步从一个顶点在一个顶点在U中中，而，而另一个顶另一个顶点不在点不在U中中的各条边中选择的各
12、条边中选择权值最小的边权值最小的边(u, v),把它的顶点加入到把它的顶点加入到集合集合U中。如此继续下去，中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集直到网络中的所有顶点都加入到生成树顶点集合合U中为止。中为止。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。用普里姆算法构造最小生成树的过程用普里姆算法构造最小生成树的过程在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组： lowcost 存存放放生生成成树树顶顶点点集集合合内内顶顶点点到到生生成成树外各顶点树外各顶点的各边上的当前最小权值；的各边上的当前最小权值； nearvex 记记录录生生
13、成成树树顶顶点点集集合合外外各各顶顶点点距距离离集合内哪个顶点集合内哪个顶点最近最近(即权值最小即权值最小)。例子例子若选择从顶点若选择从顶点0出发，即出发，即u0 = 0，则两个辅助数则两个辅助数组的初始状态为：组的初始状态为：然后反复做以下工作：然后反复做以下工作： 在在 lowcost 中选择中选择 nearvexi - -1 & lowcosti最小最小的边的边 i 用用 v 标记它。则选中的权值最小的边为标记它。则选中的权值最小的边为 (nearvexv, v)，相应的权值为相应的权值为 lowcostv。 将将 nearvexv 改为改为 - -1, 表示它已加入生成树顶点表示它已
14、加入生成树顶点集合。将边集合。将边 ( nearvexv, v, lowcostv ) 加入生加入生成树的边集合。成树的边集合。 取取 lowcosti = min lowcosti, Edgevi ，即即用用生成树顶点集合外各顶点生成树顶点集合外各顶点 i 到到刚加入该集合刚加入该集合的新顶点的新顶点 v 的距离的距离 Edgevi 与原来它们到生与原来它们到生成树顶点集合中顶点的最短距离成树顶点集合中顶点的最短距离lowcosti 做比做比较较, 取距离近的作为这些集合外顶点到生成树取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。顶点集合内顶点的最短距离。 如果如果生成树顶点
15、集合外顶点生成树顶点集合外顶点 i 到到刚加入该集合刚加入该集合的新顶点的新顶点 v 的距离比原来它到生成树顶点集合的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改中顶点的最短距离还要近，则修改nearvexi：nearvexi = v。表示生成树外顶点表示生成树外顶点i到生成树内到生成树内顶点顶点v当前距离最近。当前距离最近。继续重复得继续重复得：顶点顶点5加入生成树顶点集合：加入生成树顶点集合：v = 5v = 4最后生成树中边集合里存入得各条边为最后生成树中边集合里存入得各条边为：(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (
16、2, 1, 16), (1, 6, 14)利用普里姆算法建立最小生成树利用普里姆算法建立最小生成树void Graph :Prim ( MinSpanTree &T ) int NumVertices = VerticesList.last; /图顶点数图顶点数 float * lowcost = new floatNumVertices; int * nearvex = new intNumVertices; for ( int i = 1; i NumVertices; i+ ) lowcosti = Edge0i; /顶点顶点0到各边的代到各边的代价价 nearvexi = 0; /及最
17、短带权路径及最短带权路径 nearvex0 = -1; /顶点顶点0加到生成树顶点集加到生成树顶点集合合 MSTEdgeNode e; /最小生成树结点辅助单元最小生成树结点辅助单元 for ( i = 1; i NumVertices; i+ ) /循环循环n- -1次次, 加入加入n- -1条边条边 float min = MAXNUM; int v = 0; for ( int j = 0; j NumVertices; j+ ) if ( nearvexj != -1 & lowcostj min ) v = j; min = lowcostj; /求生成树外顶点到生成树内顶点具有最小
18、求生成树外顶点到生成树内顶点具有最小 /权值的边权值的边, v是是当前具最小权值的边的位置当前具最小权值的边的位置 if ( v ) /v=0表示再也找不到要求顶点了表示再也找不到要求顶点了 e.tail = nearvexv; e.head = v; e.cost = lowcostv; T.Insert (e); /选出的边加入生成树选出的边加入生成树 nearvexv = -1; /作该边已加入生成树标记作该边已加入生成树标记 for ( j = 1; j NumVertices; j+ ) if ( nearvexj != -1 & / j 不在生成树中不在生成树中 Edgevj lowcostj ) /需要修需要修改改 lowcostj = Edgevj; nearvexj = v; 分析以上算法，设连通网络有分析以上算法，设连通网络有 n 个顶点个顶点 ，则该算法的时间复杂度为，则该算法的时间复杂度为 O(n2), 它适用于边稠密的网络。它适用于边稠密的网络。
