最小生成树.

Presentation on theme: "最小生成树."— Presentation transcript:

1 最小生成树

2 最小生成树 ( minimum cost spanning tree )
使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。 构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点； 不能使用产生回路的边。

3 算法的框架 我们利用最小堆(MinHeap)和并查集(DisjointSets)来实现克鲁斯卡尔算法。
克鲁斯卡尔 (Kruskal) 算法 克鲁斯卡尔算法的基本思想： 设有一个有 n 个顶点的连通网络 N = { V, E },最初先构造一个只有 n 个顶点，没有边的非连通图 T = { V,  }, 图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。 算法的框架 我们利用最小堆(MinHeap)和并查集(DisjointSets)来实现克鲁斯卡尔算法。

4 首先，利用最小堆来存放E中的所有的边, 堆中每个结点的格式为
在构造最小生成树的过程中，最小堆中存放剩余的边，并且利用并查集的运算检查依附于一条边的两个顶点 tail、head 是否在同一个连通分量 (即并查集的同一个子集合) 上, 是则舍去这条边；否则将此边加入 T，同时将这两个顶点放在同一个连通分量上。随着各边逐步加入到最小生成树的边集合中，各连通分量也在逐步合并，直到形成一个连通分量为止。 tail head cost 边的两个顶点位置 边的权值

5 应用克鲁斯卡尔算法构造最小生成树的过程

6 最小生成树类定义 const int MAXINT = 机器可表示的, 问题中不可 能出现的大数 class MinSpanTree; class MSTEdgeNode { //生成树边结点类定义 friend class MinSpanTree; private: int tail, head; //生成树各边的两顶点 float cost; //生成树各边的代价 };

7 class MinSpanTree { //生成树的类定义
public: MinSpanTree ( int sz = NumVertices -1 ) : MaxSize (sz), n (0) { edgevalue = new MSTEdgeNode[MaxSize]; } int Insert ( MSTEdgeNode & item ); //将item加到最小生成树中 protected: MSTEdgeNode *edgevalue; //边值数组 int MaxSize, n; //最大边数,当前边数 };

8 利用克鲁斯卡尔算法建立最小生成树 void Graph<string, float> :: Kruskal ( MinSpanTree& T ) { MSTEdgeNode e; //边结点辅助单元 MinHeap<MstEdgeNode> 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 ( Edge[u][v] != MAXNUM ) { //所有边 e.tail = u; e.head = v; e.cost = Edge[u][v]; H.Insert (e); //插入堆 }

9 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 ); //该边存入最小生成树 T count++; }

10 出堆顺序 (0,5,10) 选中 (2,3,12) 选中 (1,6,14) 选中 (1,2,16) 选中 (3,6,18) 舍弃
出堆顺序 (0,5,10) 选中 (2,3,12) 选中 (1,6,14) 选中 (1,2,16) 选中 (3,6,18) 舍弃 (3,4,22) 选中 (4,6,24) 舍弃 (4,5,25) 选中 F     0        2       10     5    -1 -1 -1 -1 -1 -1 -1 -2 -1 -1 -1 -1 -1 -2 -1 -2 2 -1 -1 -2 -2 -2 2 -1 1 -2 -4 1 2 -1 1 -2 -5 1 2 1 1 1 -7 1 2 1 1 并查集 邻接矩阵表示

11 在建立最小堆时需要检测邻接矩阵，计算的时间代价为 O(n2)。且做了 e 次堆插入操作, 每次插入调用了一个堆调整算法FilterUp( )算法, 因此堆插入需要的时间代价为 O(elog2e)。
在构造最小生成树时，最多调用了 e 次出堆操作RemoveMin( )，2e 次并查集的Find( )操作，n-1次Union( )操作，计算时间分别为 O(elog2e)，O(elog2n)和O(n)。 总的计算时间为 O(elog2e + elog2n + n2 + n )

12 普里姆(Prim)算法 普里姆算法的基本思想： 从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 采用邻接矩阵作为图的存储表示。

13 用普里姆算法构造最小生成树的过程

14 在构造过程中，还设置了两个辅助数组： 例子 lowcost[ ] 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；
nearvex[ ] 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。 例子

15 若选择从顶点0出发，即u0 = 0，则两个辅助数组的初始状态为：
然后反复做以下工作： 在 lowcost [ ]中选择 nearvex[i]  -1 && lowcost[i]最小的边 i 用 v 标记它。则选中的权值最小的边为 (nearvex[v], v)，相应的权值为 lowcost[v]。 将 nearvex[v] 改为 -1, 表示它已加入生成树顶点集合。将边 ( nearvex[v], v, lowcost[v] ) 加入生成树的边集合。

16 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 v 的距离 Edge[v][i] 与原来它们到生成树顶点集合中顶点的最短距离lowcost[i] 做比较, 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。 如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 v 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改nearvex[i]：nearvex[i] = v。表示生成树外顶点i到生成树内顶点v当前距离最近。

17 v = 5 顶点5加入生成树顶点集合： v = 4 继续重复得：

18 最后生成树中边集合里存入得各条边为： (0, 5, 10), (5, 4, 25), (4, 3, 22), (3, 2, 12), (2, 1, 16), (1, 6, 14) 利用普里姆算法建立最小生成树 void Graph<string, float> :: Prim ( MinSpanTree &T ) { int NumVertices = VerticesList.last; //图顶点数 float * lowcost = new float[NumVertices]; int * nearvex = new int[NumVertices]; for ( int i = 1; i < NumVertices; i++ ) { lowcost[i] = Edge[0][i]; //顶点0到各边的代价 nearvex[i] = 0; //及最短带权路径 }

19 nearvex[0] = -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 ( nearvex[j] != -1 && lowcost[j] < min ) { v = j; min = lowcost[j]; } //求生成树外顶点到生成树内顶点具有最小 //权值的边, v是当前具最小权值的边的位置 if ( v ) { //v==0表示再也找不到要求顶点了 e.tail = nearvex[v]; e.head = v;

20 T.Insert (e); //选出的边加入生成树 nearvex[v] = -1; //作该边已加入生成树标记
e.cost = lowcost[v]; T.Insert (e); //选出的边加入生成树 nearvex[v] = -1; //作该边已加入生成树标记 for ( j = 1; j < NumVertices; j++ ) if ( nearvex[j] != -1 && // j 不在生成树中 Edge[v][j] < lowcost[j] ) { //需要修改 lowcost[j] = Edge[v][j]; nearvex[j] = v; } 分析以上算法，设连通网络有 n 个顶点 ，则该算法的时间复杂度为 O(n2), 它适用于边稠密的网络。