最小生成树PPT演示最终

背景知识
• 最小生成树：在连通边赋权图G 中求一棵总权值 最小的生成树 。该生成树称为最小生成树或 最小代价树。
构造最小生成树的思想
• 构造最小生成树可以有多种算法。其中多数 算法利用了最小生成树的一种简称为MST的 性质：假设N=(V,{E})是一个连通网(v代表顶点 集，E代表边集)，U是顶点集V的一个非空子 集。若(u,v)是一条具有最小权值的边，其中 u∈U，v∈V-U,则必存在一棵包含边(u,v)的最 小生成树。
5 4
V4
3
V5
2
V6
1 edgeco st adjvex 1 v1,v 3 2 2 v4,v 6 3 3 v2,v 5 4 4 v3,v 6 5 5 v3,v 4 6 5 v2,v 3
6
V1
6
V2
5
5 6 1
V3
5
V4
3
V5
4
6
V6
2
1 edgeco st adjvex 1 2 2 3 3 4 4 5 5 6 5 v2,v 3
普里姆算法
• 利用该图 按普里姆 算法构造 一棵最小 生成树
6 5 3
5 1
5
4 2
6 6
V1
6Leabharlann V251 5V3
5
V4
3
V5
i
v2 closedge adjvex lowcost
V1 6 V1 1
6 6
4
V6
v6
2
v3
v4
V1 5
v5
U
{V1}
V-U
{V2,V3 ,V4,V5, V6}
k
v3
V1
v4,v6 v5,v6
利用堆排序后结果：
1 edgecost adjvex 1 v1,v3 2 2 v4,v6 3 3 v2,v5 4 4 v3,v6 5 5 v3,v4 6 5 v2,v3 7 5 v1,v4 8 6 v3,v5 9 6 10 6
v5,v6 v1,v2
V1
6
V2
5
5 6 1
V3
普里姆算法分析
• 假设网中有n个顶点，则第一个进行初 始化的循环语句的频度为n，第二个循 环语句的频度为n-1；其中有两个内循 环：其一是在closedge[v].lowcost中求 最小值，其频度为n-1;其二是重新选择 具有最小代价的边，其频度为n。由此 ，普里姆算法的时间复杂度为O(n²),与 网中的边数无关，因此适用于求边稠 密的网的最小生成树。
Solin 算法
Rosenstiehl
和 管梅谷 算法
Dijkstra 算法
最小生成树的其他求解方法
Solin算法
• 此算法的基本思路是：将求连通带权图的最 小生成树的过程分为若干阶段，每一阶段选 取若干条边。具体步骤如下： • （1）将每个顶点视为一棵树，图中所有顶点 视为一个森林； • （2）为每棵树选取一条边，它是该树与其他 树相连的所有边中权值最小的一条边，把该 边生成树中。如果某棵树选取的边已经被其 他树选过，该边不再选取。整个森林变成一 棵树。 • 重复操作（2），直到整个森林变成一棵树。
克鲁斯卡尔算法
• 克鲁斯卡尔算法从另一途径求网的最小生 成树。假设连通网N=(V,{E}),则令最小生成树 的初始状态为只有n个顶点而无边的非连通 图T=(V,{}),图中每个顶点自成一个连通分量 。在E中选择代价最小的边，若该边依附的 顶点落在T中不同的连通分量上，则将此边 加入到T中，否则舍去此边而选择下一条代 价最小的边。以此类推，直至T中所有顶点 都在同一连通分量上为止。
讨论课题：
最小生成树的求解方法与分析
目录
01
02
背景知识
03
最小生成树的求 解方法与分析
组内成员 分工介绍
组内成员及分工介绍：
组 长
组 员
组 员
组 员
组 员
刘先喆： 陈静： 何安琪： 韩佳文： 编写最小 汇报演讲、 制作PPT、 撰写报告 生成树求 制作PPT 分析算法、 提问问题 解方法、 探索其他 回答问题 解决方法
0
0
6
0
V1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost 0 0 v3
6 6
4
V6
v6
2
v4
v5
U
V-U
k
V2
0
3
0
{V1,V3 ,V6,V4, V2}
{V5}
v5
V1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost 0 0 v3
克鲁斯卡尔算法
• 利用该图 按克鲁斯 卡尔算法 构造一棵 最小生成 树
6 5 3
5 1 5 4 2
6 6
各边权值的堆排
6 1 5 4
1 edgecost adjvex 6 v1,v2 2 1 v1,v3
5 3 5 6
2
3 5 v1,v4
6
4 5 v3,v4 5 3 v2,v5 6 5 v2,v3 7 6 v3,v5 8 4 v3,v6 9 2 10 6
Dijkstra算法
• Dijkstra算法的基本思路是；对于一个连通 网络N={V,E},把E中所有 的边以方便的次序 逐个加入到初始值为空的生成树的边集合T 中。每次选择并加入一条边时，需判断它 是否与先前加入T中的边构成回路。如果构 成了回路，则从这个回路中将权值最大的 边退选。如此重复，直到T中有n-1条边为止 ，其中n是V中顶点个数。
v4,v v2,v 6 5
v3,v v2， 4 v3
V1
6
V2
5
5 5 6 1
V3
5
V4
3
V5
4
6
V6
2
1 edgeco st adjvex 1 v1, v3 2 2 3 3 4 4 v3, v6 5 5 v3, v4 6 5 v2,v 3
v4,v v2,v 6 5
克鲁斯卡尔核心算法
• for(i=0;i<G.vexnum;i++)//各顶点集初始化 • flag[i]=i; • for(i=G.arcnum,count=1;count<G.vexnum;i--) • { • j=G.arcs[i].v1;k=G.arcs[i].v2; • if(flag[j]!=flag[k])//两个点属于不同集合 • { • printf("(%s-%s)%d\n",G.vexs[j],G.vexs[k],G.arcs[i].value); • count++; • for(l=0;l<G.vexnum;l++) • if(flag[l]==flag[k])//将点k所在集合的点并入j所 在集合 • flag[l]=flag[j]; • } • }
v1,v v4,v 3 6
v2,v v3,v v3,v 5 6 4
V1
6
V2
5
5 6 1
V3
5
V4
3
V5
4
6
V6
2
1 edgec ost adjvex 1 v1, v3 2 2 v4,v 6 3 3 4 4 5 5 6 5 v2,v 3
v2,v v3,v v3,v 5 6 4
V1
6
V2
5
5 6 1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost
V3 5 0
6 6
4
V6
v6
V3 4
2
v3
v4
V1 5
v5
V3 6
U
{V1, V3}
V-U
{V2,V4 ,V5,V6}
k
v6
V1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost
V3 5
李昕翼： 撰写报告 提问问题
最小连接问题
• 交通网络中，常常关注能把所有站点连接 起来的生成树，使得该生成树各边权值之 和为最小。例如：
• 假设要在某地建造5个工厂，拟修筑道路连接这5 处。经勘探，其道路可按无向边铺设。现在每条 边的长度已经测出并标记在对应边上，如果我们 要求铺设的道路总长度最短，如何铺设？
6 6
4
V6
v6
2
v4
v5
U
V-U
{}
k
0
0
0
{V1,V3,V 6,V4,V2, v5}
普里姆核心算法
• // 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 • void MiniSpanTree_PRIM(MGraph G,VertexType u) • { • int i,j,k; • Closedge closedge; • k=LocateVex(G,u); • for(j=0;j<G.vexnum;++j) // 辅助数组初始化 • { • if(j!=k) • { • strcpy(closedge[j].adjvex,u); • closedge[j].lowcost=G.arcs[k][j].adj; • } • } ..\..\普里姆算法\普里姆 .cpp
• closedge[k].lowcost=0; // 初始时,U={u} • printf("最小代价生成树的各条边为:\n"); • for(i=1;i<G.vexnum;++i) • { // 选择其余G.vexnum-1个顶点 • k=MiniNum(closedge,G); // 求出T的下一个结点：第K顶点 • printf("(%s%s)%d\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); // 输出生成树的边 • closedge[k].lowcost=0; // 第K顶点并入U集 • for(j=0;j<G.vexnum;++j) • if(G.arcs[k][j].adj<closedge[j].lowcost) • { • // 新顶点并入U集后重新选择最小边 • strcpy(closedge[j].adjvex,G.vexs[k]); • closedge[j].lowcost=G.arcs[k][j].adj; • } • } • }