06树与流XXXXBIG学习课件.pptxVIP

通信网络理论基础王晟博士教授博导Part06:树与流

2014年春季通信网络理论基础2/50树与流1最小生成树算法最小生成树的各种解法突出地显示了贪婪算法的力量。2最大流算法

3/50最小生成树算法Prim算法请着重体会：最优条件与算法的关系.Sollin算法Kruskal算法割最优条件路径最优条件采用类似思路二者等价SPH算法综合了两个算法的思路2014年春季通信网络理论基础

4/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础

路径最优条件5/5012345691078事实对每条非树上边e(k,l)，都必然存在唯一一条由树上边构成的路径p(k,l)连接顶点k和顶点l。：树上边：非树上边路径最优条件一棵生成树为最小生成树的充要条件是：任一非树上边的权重都大于它所对应的树上路径上的每条边的权重。2014年春季通信网络理论基础

树上边与割集6/5012345691078：树上边：非树上边S2S1割集删除任意一条树上边e(i,j)，都会将原图划分为两个部分。原图中连接这两个部分的边（包括树上边和非树上边）的集合，称为割集。事实每条树上边e(i,j)都对应一个割集。2014年春季通信网络理论基础

割最优条件7/50一棵生成树为最小生成树的充要条件是：任一树上边的权重都小于它所对应的割集中每条边的权重。割最优条件12345691078S2S1事实每条树上边e(i,j)都对应一个割集。：树上边：非树上边2014年春季通信网络理论基础

8/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础

从最优条件到算法9/50路径最优条件从一棵生成树开始，检查其非树上边；一旦发现最优条件被违背，则替换；直至所有的非树上边都满足该条件。不能保证多项式时间。请通过Kruskal的思想来体会一下数据结构在算法设计中的重要性。2014年春季通信网络理论基础

10/50Kruskal算法思想若该边的两个端点属于不同的树，就合并这两棵树；若属于同一棵树，就删除该边，继续检查；把原图中所有边按权重的升序排序；一开始把原图看作一个森林，含n棵树；按序、逐条地检查边：直至只剩下一棵树（或者留下来的边的数目为n–1）。为啥不检查完所有的边？剩下没检查的边都必然是非树上边，且权重更大。2014年春季通信网络理论基础

路径最优条件在哪里？11/50跟路径最优条件有啥关系？Kruskal算法中被排除的边是什么样的边？是那种两个端点已经在同一树上的边。即非树上边。根据路径最优条件，什么时候应该排除非树上边e(i,j)？当树上路径P(i,j)中的每条边的权重都小于e(i,j)时。Kruskal算法中，为啥不用做这样的比较？因为所有的边已排序。结论：由于路径最优条件，所以Kruskal算法是正确的。2014年春季通信网络理论基础

一个例子12/50bacd3525e4020101530bacde101520352014年春季通信网络理论基础

Kruskal算法实现13/50怎样检查边是否属于树？怎样进行树的归并？每棵树都用一个顶点的list来表达，并记录该list的size和last。每个顶点都附加一个变量first，用于记录该顶点所在的list的第一个顶点。数据结构设计请再次体会数据结构的力量：采用下述数据结构设计后，复杂度从O(nm)降为O(m+nlogn)。怎样检查边是否属于树？看两个顶点的first是否相同。怎样进行树的归并？比较size；将较小的树插入到较大的树后面（last）。为什么要把大的放在前面？因为排在后面的list中的顶点都要更新其first值。2014年春季通信网络理论基础

14/50最小生成树算法4最优性条件1235Kruskal算法Prim算法Sollin算法Steiner树问题2014年春季通信网络理论基础

Prim算法15/50路径最优条件割最优条件Kruskal算法Prim算法基本思想：从某个顶点（初始树）出发，一次增加一条边到树上，直至最后。哪个顶点？随便哪个都行。哪条边？假定已在树上的顶点集合为S，那么每次循环中得到的S和V–S就定义了原图的一种划分。对应这种划分，必有一个割集。根据割最优条件，应该选该割集中权重最小的边。bacd3525e40201015302014年春季通信网络理论基础

Prim算法伪码16/50FORallvertexjinVDOd(j)=?;p(j)=NULL;S={s};d(s)=0;p(s)=NU