图论课件--最小生成树共37页文档

格式：ppt
大小：3.32 MB
文档页数：37

下载文档原格式

/ 37

第十二章(最小生成树)

第十二章最小生成树路；连通图；圈。

树：连通，且不含圈。

一个树中：点个数减1等于边个数。

若图G中的一个树包含了G的全部顶点（通常会少一些边），则称该树为图G的一个生成树。

同一个图可能有多个生成树，比较每个生成树的权，最小者称为最小生成树。

求一个给定图的最小生成树：法一：Kruskal算法（1）全部边，按权全从小到大排列，取出第一个边放入集合T ；（2）从剩余的边中取出权最小的，若该边与T中边能组成圈，则去掉该边，否则将该边放入集合T ；（3）重复（2）的工作，直至全部顶点出现，则T 就是最小生成树。

法二：Prim算法（1）从顶点集V中任取一个顶点，放入集合S；（2）考虑V\S的点与S的点之间的边，从中取权最小者放入集合T，对应的点放入S；（3）重复（2），直至S包含全部顶点，则T就是最小生成树.手工做Kruskal或Prim计算都很容易，但只适用于规模小（即：顶点数、边数都不大）的图。

例：手工做P189之操练题。

更重要的，还是用机器做：1．用Matlab实现Kruskal算法输入“边权矩阵”b，顶点数n，将b的列，按第三行从小到大排序，命令为b=sortrows(b’,3)’关键是如何让机器识别“某个边是否与T中边组成圈”。

这样设计：共有n个顶点1,2,…,n，用t表示i顶点i的标记，初始令it；集合T中边的任何一组i端点，只要它们沿着T中的路连通就令它们的标记相同，都等于这组端点的最小标记；对于T外的一条边，“它与T中边组成圈”的充分必要条件是“它的两个端点的标记相等”。

下面程序（函数M---文件）就是根据“边权矩阵”b用Kruskal算法给出最小生成数T：function [T,quan]=syp175hswj(b)n=max(max(b(1:2,:)));m=length(b(1,:));b=sortrows(b',3)';t=1:n;k=0;quan=0;for j=1:mif t(b(1,j))~=t(b(2,j))k=k+1;T(k,:)=b(:,j)';quan=quan+b(3,j);xbh=min(t(b(1,j)),t(b(2,j)));dbh=max(t(b(1,j)),t(b(2,j)));for i=1:nif t(i)==dbht(i)=xbh;endendendif k==n-1breakendend如：输入P172图12.1的边权矩阵b=[1,1,1,2,2,3,3,4;2,4,5,3,5,4,5,5;8,1,5,6,7,9,10,3]；再调用函数文件[T,quan]=syp175hswj(b)输出结果：T =1 4 14 5 32 3 62 5 7quan =17再做P189之操练题：b=[1,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,9,10;2,8,9,3,9,4,10,5,11, 6,11,7,11,8,10,9,10,11;2,1,8,1,6,2,3,9,7,4,2,1,1,9,4,7,1,6]; [T,quan]=syp175hswj(b)输出结果：T =1 8 12 3 16 7 16 11 19 10 11 2 23 4 25 11 23 10 37 10 4quan =182．用Matlab实现Prime算法Prime算法的函数文件：function [T,quan]=syp177hswj(a)n=length(a(1,:));lh=ones(1,n);lh(1)=0;gs=1;k=0;quan=0; while gs<nzx=Inf;for i=1:nfor j=1:nif lh(i)==0&lh(j)==1&a(i,j)<zxzx=a(i,j);zxi=i;zxj=j;endendendlh(zxj)=0;k=k+1;gs=gs+1;quan=quan+zx;T(k,:)=[zxi,zxj,zx];end书P177之例2：cleara=[0,8,Inf,1,5;8,0,6,Inf,7;Inf,6,0,9,10;1,Inf,9,0,3;5,7,10,3, 0];[T,quan]=syp177hswj(a)书P189之Prime算法：cleara=ones(11,11)*Inf;for i=1:11a(i,i)=0;enda(1,2)=2;a(1,8)=1;a(1,9)=8;a(2,3)=1;a(2,9)=6;a(3,4)=2;a( 3,10)=3;a(4,5)=9;a(4,11)=7;a(5,6)=4;a(5,11)=2;a(6,7)=1; a(6,11)=1;a(7,8)=9;a(7,10)=4;a(8,9)=7;a(9,10)=1;a(10,11 )=6;a(2,1)=2;a(8,1)=1;a(9,1)=8;a(3,2)=1;a(9,2)=6;a(4,3)=2;a( 10,3)=3;a(5,4)=9;a(11,4)=7;a(6,5)=4;a(11,5)=2;a(7,6)=1; a(11,6)=1;a(8,7)=9;a(10,7)=4;a(9,8)=7;a(10,9)=1;a(11,10 )=6;[T,quan]=syp177hswj(a)。

4最小生成树

v3 v6
特点——边少、点不少。图为根植于v2的DFS-树
图的生成树(spanning tree)
广度优先算法：
—— 图G′ 与图G的点集相同，但图G′ 的边集仅是图G边集的子集。
v1 v7
v2
v5
生成树：设图T＝(V，E′)是图 G＝(V，E)的生成子图，如 v4 果T是一个树，则称 T 是 G 的一个生成树（支撑树）。
3
5
1 v4
v3
2
7 5 3 5 v5
v6
1 7
5
v7
最小部分树如图上红线所示；最小权和为14。思考：破圈法与避圈法各自的思路是怎样做的呢？ ——见圈就破，去掉其中权最大的。 ——加边取其中最小的。
最小生成树的算法
例要在5个城市架设电话线，使城镇之间能够通话两镇直接连接，每两个城镇之间的架设电话线的造价如下图所示，各边上的数字为造价（单位：万元）。问：应如何架线，可使总造价最小？
树的性质
3) 设图G＝(V，E)是一个树，点数n(G) ≥ 2，则 G 中至少有两个悬挂点（叶子）。从一棵n阶树中删除一片叶子之后得到n-1阶树。 5) 图G＝(V，E)是一个树，|V|=n，|E|=m <==>G是连通图，且不含圈 <==>G的任意两个顶点之间有且仅有一条路径 <==>G是连通图，且m＝n－1 <==>G无圈，且m＝n－1 <==>G无圈，但在G的任意两个不相邻的顶点之间增加一条边，则得到唯一的一个圈 <==> G是连通图，且G的每条边都是割边（桥），即删去G的任意一条边后所得的图都不连通。
∵图中已经不含圈
且 n＝ 5 m＝4

《图论最小生成树》课件

图论最小生成树
在计算机科学中，图论最小生成树是一种常见的算法，用于在给定的加权图中找到一棵包含所有顶点的最小权重树。
什么是图论最小生成树
1 定义
图论最小生成树是指在一个图中，找到一棵包含所有顶点的且边的权重之和最小的树。
2 应用
最小生成树常用于网络设计、链路优Байду номын сангаас、行程规划等问题。
如何生成最小生成树
1
Kruskal算法
2
按照边权重递增的顺序选择边，直到最
小生成树中包含所有顶点。
3
Prim算法
从一个顶点开始，逐步扩展最小生成树，直到包含所有顶点。
其他算法
除了Prim和Kruskal算法，还有其他一些生成最小生成树的算法，如Boruvka算法和BFS算法。
最小生成树与带权图
最小生成树算法通常用于带权图，这种图中的边带有权重，代表顶点之间的关系强度或代价。
应用实例
网络设计
在计算机网络中，最小生成树可用于确定网络拓扑，优化链路和路由。
城市规划
通过最小生成树算法，可以确定城市道路的规划和建设顺序。
行程规划
最小生成树可在旅行规划中，帮助确定最短路径和最优路线。
总结和提高建议
1 重要性
最小生成树在图论和算法设计中扮演着重要的角色。
2 优化算法
不同的最小生成树算法在效率和应用场景上有所不同，需要根据具体情况选择合适的算法。

第3讲最小生成树

介绍最小树的两种算法：介绍最小树的两种算法： Kruskal算法和算法和Prim破圈法破圈法. 算法和破圈法
T
A Kruskal算法（或避圈法）算法（或避圈法）算法步骤如下：步骤如下： 1) 选择边 1，使得 1)尽可能小；选择边e 使得w(e 尽可能小尽可能小； 2) 若已选定边 e1, e2 ,..., ei ，则从 E \ {e1, e2 ,..., ei } 使得: 中选取ei +1 ，使得 i) G[{e1, e2 ,..., ei +1}] 为无圈图，为无圈图， ii) w(ei +1 ) 是满足的尽可能小的权，是满足i)的尽可能小的权的尽可能小的权， 3) 当第步不能继续执行时，则停止当第2)步不能继续执行时则停止. 步不能继续执行时，定理由Kruskal算法构作的任何生成树算法构作的任何生成树 T * = G[{e1, e2 ,..., eν −1}] 都是最小树都是最小树.
v1
v2
v3
v4
v5
平凡树
（2）找图中生成树的方法）可分为两种：可分为两种：避圈法和破圈法 A 避圈法 : 深探法和广探法 B 破圈法
A 避圈法定理3的充分性的证明提供了一种构造图的生定理的充分性的证明提供了一种构造图的生成树的方法. 成树的方法这种方法就是在已给的图G中这种方法就是在已给的图中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为条边使它与已选边不构成圈，直到选够条边为这种方法可称为“避圈法” 加边法” 止. 这种方法可称为“避圈法”或“加边法” 在避圈法中，按照边的选法不同，在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法. 成树的方法可分为两种：深探法和广探法

图论课件--最小生成树共37页

1、最灵繁的人也看不见自己的背脊。——非洲 2、最困难的事情就是认识自己。——希腊 3、有勇气承担命运这才是英雄好汉。——黑塞 4、与肝胆人共事，无字句处读书。——周恩来 5、阅读使人充实，会谈使人敏捷，写作使人精确。——培根

图论课件--最小生成树
1、纪律是管理关系的形式。——阿法纳西耶夫 2、改革如果不讲纪律，就难以成功。
3、道德行为训练，不是通过语言影响，而是让儿童练习良好道德行为，克服懒惰、轻率、不守纪律、颓废等不良行为。 4、学校没有纪律便如磨房里没有水。 ——夸美纽斯
5、教导儿童服从真理、服从集体，养成儿童自觉的纪律性，这是儿童道德教育最重要的部分。—— 陈鹤琴

图论课件--最小生成树37页PPT

9
6
63
2
7
2
10
3
4
3
1
用算法求出的生成路为：
9
6 3
2 2
1 12
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
直接在图中选出的一条生成路为：
6
63
2
3 1
后者的权值小于前者。
(二)、管梅谷的破圈法
在克鲁斯克尔算法基础上，我国著名数学家管梅谷教授于1975年提出了最小生成树的破圈法。
解：过程如下：
1
v1
2
v5
v8
1 v5
v1
2
v8
1 v5
v1
2
3
1
v5
v8
5
v7
v4 v1
2
3
1
v5
v8
5
v7
v4 3 v8
v4
6
v3
8
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
v1
v1
v4
2
v4 3
2
3
1
v5
v8
1
v5
v8
5
6
5
6
v6 8
v7
v6 8
图论课件--最小生成树
1、舟遥遥以轻飏，风飘飘而吹衣。 2、秋菊有佳色，裛露掇其英。 3、日月掷人去，有志不获骋。 4、未言心相醉，不再接杯酒。 5、黄发垂髫，并怡然自乐。

最小生成树-数学建模.ppt

用Kruskal算法可求出最小生成树，在前面给出的Kruskal算法的MATLAB程序中，边权矩阵b 的值改为此处的边权矩阵，顶点数n改为9即可。
上一页下一页主页
T= 7 8 15 12 39 46 47 45 13
c = 4.4300
机器的分组：{3， 9}，
{1，2，5}，
{4，6，7，8}。
返回
整理边权矩阵
初始化：j0, T, c0, k0；对所有顶点i ,t(i)i .
B: 图的边权矩阵; T: 生成树的边集; C: 生成树的权; t: 顶点所属子树的编号
jj+1
t(B(1,j))t(B(2,j)) Y
N
TT(B(1,j),B(2,j)), cc+B(3,j),kk+1，i 0
i i+1
引例：计算机网络的线路设计
最小生成树
最大生成树 1) 一个完全图Kn有多少不同的生成树？ 2) 如何求其最小生成树?
引例：计算机网络的线路设计
10个顶点的完全图，其不同的生成树就有一亿棵。
一般地，n个顶点的完全图，其不同的生成树个数为nn-2。
30 个顶点的完全图就有 3028 个生成树，求最小生成树时用穷举法是无效的。
假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。
范例：制造系统的分组技术
机器 1 2 3 4 5 6 7 8 9
加工 2,3, 2,7, 1,6 3, 3,7, 5 4, 4, 6
的零 7,8, 8, 件 9, 11,1
12, 2
5, 8,9, 10 12,
13
10 10
3

03 最小生成树

6 2 3 5 3 6 5 6 4 6 1 1 5 5 4 2 5 6 2 1 3 4
所选的边都是一端一端在 1. 所选的边都是一端在V-U中，另一端在U中；中另一端在中 2. 从一个顶点开始逐步增加中的顶点，Prim算法可称为“加点从一个顶点开始逐步增加U中的顶点中的顶点，算法可称为“ 算法可称为法”。
普里姆(Prim)算法过程示例普里姆(Prim)算法过程示例 (Prim)
28 1 10 6 25 25 5 22 4 14 7 18 2 16 3 12
普里姆(Prim)算法过程示例普里姆(Prim)算法过程示例 (Prim)
28 1 10 6 25 25 5 22 4 14 7 18 2 16 3 12
A B C D E B C
A D E B C
A D E
F 图G
G
F
G
F
G
图G的生成树的生成树
图G的又一生成树的又一生成树
1. 如果在一棵生成树上添加一条边,必定构成一个环；如果在一棵生成树上添加一条边必定构成一个环添加一条边必定构成一个因为这条边使得它依附的那两个顶点之间有了第二条路径。条路径。 2. 一棵有个顶点的生成树连通无回路图)有且仅有一棵有n个顶点的生成树连通无回路有且仅有个顶点的生成树(连通无回路图有且仅有(n条边,则是 1)条边如果一个图有个顶点和小于条边,如果一个图有个顶点和小于条边条边如果一个图有n个顶点和小于(n-1)条边则是非连通图。如果它多于连通图。如果它多于(n-1)条边则一定有回路。条边,则一定有回路。多于条边则一定有回路 3. 有(n-1)条边的图不一定都是生成树。条边的图不一定都是生成树。条边的图不一定都是生成树

牛小飞《数据结构》9.5最小生成树

二、算法
图的遍历算法访问了图中的每个顶点一次且仅一次。
访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。
生成树算法
void DFSTree(AdjGraph G,int v,CSNode T){ 算法以孩子 G.vertexs[v].visited=true; first=true; 兄弟链表作 for(w=FirstAdjVex(G,v);w>=0; 为生成森林 w=NextAdjVex(G,v,w)) 的存储结构 if(! G.vertexs[w].visited){ p= new CSNode(G.vertexs[w].data); V if(first){ T.lchild=p;first=false; } w3 w w 2 1 else{ q.nextsibling=p;} q=p; DFSTree(G,w.q); SG3 SG1 SG2 } }
2.最小生成树无圈。
3.最小生成树是包含所有顶点的的最小的树。
最小生成树
算法一：破圈法算法二：普里姆算法Prim
算法三：克鲁斯卡尔算法Kruskal
破圈法
一、基本思想
1、将所有的边按权重从大到小排列。
2、对每条边e尝试下面的操作，直到G中的边数=n-1:
如果删除e, 图G仍然是连通图，则从G中删除e
网的边上的权值：通信代价
v6
v7
最小生成树
v1
4 1 2 5 8
2
3
v2
10 7 4 6
v1
1 2
2
v2
v3
v4
1
v5
v3
v4
4
v5

最小生成树MinimumSpanningTree

1
MST性质－大多数算法都利用了此性质
设G＝(V，E)是一连通图，U是V的真子集，若（u， v）是所有连接U和V-U的边中权最小的边（轻边），则一定存在G的一棵最小生成树包括此边。
Pf：设G的任何一棵最小生成树均不包括(u，v)；
u
v
u’
T
v’
U
V-U
T’
u
v
u’
v’
U
V-U
2
构造MST：
11
1、Prim算法
算法求精－调整候选轻边集
设轻边（u,v）涂红后加入到树边中，T[k..n-2]是待调整的候选轻边集，则须根据新红点v调整T[k..n-2] 。
void ModifyCandidateSet ( AdjMatrix G, MST T, int k, int v) {
int i, d; //v是新红点 for (i=k; i<n-1; i++) { //遍历候选集
❖ 集合A上的关系R是对称的，若xRy，则yRx。其中，x，y ∈A。
❖ 集合A上的关系R是反对称的，若xRy，yRx,则必有x＝y.其中x,y ∈A。
❖ 集合A上的关系R是传递的，若xRy，yRz，则xRz。其中x,y,z ∈A。
❖ 例子：
数之间的相等关系，具有自反性，对称性，传递性，反对称性；
数之间的小于关系，具有传递性，反对称性；
int fromvex, tovex; //起点、终点 int len; //边长度，权值 } MST[n-1];
设邻接矩阵初值：不存在的边其权值为Infinity
9
1、Prim算法
算法求精－初始化
将根r涂红加入红点集U，TE＝φ。对每个白点i (0≤i ≤n-1, i≠r ), i所关联的最短紫边（r,i）的长度为G[r][i], 这n-1条最短紫边构成了初始的候选轻边集。因为树边为空，故将T[0..n-2]全部用来存放候选轻边集。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

图论课件--最小生成树
16、人民应该为法律而战斗，就像为了城墙而战斗一样。 ——赫拉克利特 17、人类对于不公正的行为加以指责，并非因为他们愿意做出这种行为，而是惟恐自己会成为这种行为的牺牲者。—— 柏拉图 18、制定法律法令，就是为了不让强者做什么事都横行霸道。— —奥维德 19、法律是社会的习惯和思想的结晶。—— 托·伍·威尔逊 20、人们嘴上挂着的法律，其真实含加强。 ——德谟克利特 67、今天应做的事没有做，明天再早也是耽误了。——裴斯泰洛齐 68、决定一个人的一生，以及整个命运的，只是一瞬之间。 ——歌德 69、懒人无法享受休息之乐。——拉布克 70、浪费时间是一桩大罪过。——卢梭