《最小生成树算法及应用精品文稿.ppt》由会员分享，可在线阅读，更多相关《最小生成树算法及应用精品文稿.ppt（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最小生成树算法及应用第1页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 第2页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 二、二、求图的最小生成树算法求图的最小生成树算法 严格来说，如果图严格来说，如果图G=G=（V V，E E）是一个连通的无向图，则把它的全部顶点）是一个连通的无向图，则把它的全部顶点V V和一部分边和一部分边EE构成一个子图构成一个子图GG，即，即G=G=（V V，EE），且边集），且边集EE能将图中所有顶点连通又不形成回能将图中所有顶点连通又不形成回路，则称子图路，则称子图GG是图是图G G的一棵生成树。的一棵生成树。对于带权连通图，生成树的权即
2、为生成树中所有边上的权值总和，权值最小的对于带权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树，称为图的最小生成树。生成树，称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。第3页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 例例1 1、城市公交网、城市公交网 问题描述问题描述 有有一一张张城城市市地地图图，图图中中的的顶顶点点为为城城市市，无无向向边边代代表表两两个个城城市市间间的的连连通通关关系系，边边上上的的权权为为在在这这两两个个城城市市之之间间修修建建高高速速公公
3、路路的的造造价价，研研究究后后发发现现，这这个个地地图图有有一一个个特特点点，即即任任一一对对城城市市都都是是连连通通的的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。输入输入 n n（城市数，（城市数，1=n=1001=n=100）；）；e e（边数）；（边数）；以下以下e e行，每行行，每行3 3个数个数i,j,wi,j,wijij，表示在城市，表示在城市i,ji,j之间修建高速公路的造价。之间修建高速公路的造价。输出输出 n-1 n-1行，每行为两个城市的序号，
4、表明这两个城市间建一条高速公路。行，每行为两个城市的序号，表明这两个城市间建一条高速公路。第4页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 举例举例 下面的图（下面的图（A A）表示一个）表示一个5 5个城市的地图，图（个城市的地图，图（B B）、（）、（C C）是对图（）是对图（A A）分别进行深度优先遍历和广）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为度优先遍历得到的一棵生成树，其权和分别为2020和和3333，前者比后者好一些，但并不是最小生成树，前者比后者好一些，但并不是最小生成树，最小生成树的权和为最小生成树的权和为1919。问题分析问题分析 出发
5、点：具有出发点：具有n n个顶点的带权连通图，其对应的生成树有个顶点的带权连通图，其对应的生成树有n-1n-1条边！条边！那么选哪那么选哪n-1n-1条边呢？条边呢？设图设图G G的度为的度为n n，G=G=（V V，E E）我们介绍两种基于贪心的算法，我们介绍两种基于贪心的算法，PrimPrim算法和算法和KruskalKruskal算法。算法。第5页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 1 1、用、用PrimPrim算法求最小生成树的思想如下：算法求最小生成树的思想如下：设置一个顶点的集合设置一个顶点的集合S S和一个边的集合和一个边的集合TETE，S S和和TETE的
6、初始状态均为空集；的初始状态均为空集；选定图中的一个顶点选定图中的一个顶点K K，从，从K K开始生成最小生成树，将开始生成最小生成树，将K K加入到集合加入到集合S S；重复下列操作，直到选取了重复下列操作，直到选取了n-1n-1条边：条边：选取一条权值最小的边（选取一条权值最小的边（X X，Y Y），其中），其中XSXS，not(YS)not(YS)；将顶点将顶点Y Y加入集合加入集合S S，边（，边（X X，Y Y）加入集合）加入集合TETE；得到最小生成树得到最小生成树T=T=（S S，TETE）。如何证明如何证明PrimPrim算法的正确性呢？提示：用反证法。算法的正确性呢？提示：用
7、反证法。因为操作是沿着边进行的，所以数据结构宜采用边集数组表示法。因为操作是沿着边进行的，所以数据结构宜采用边集数组表示法。第6页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 从文件中读入图的邻接矩阵从文件中读入图的邻接矩阵g g；边集数组边集数组elistelist初始化；初始化；For i:=1 To n-1 Do For i:=1 To n-1 Do Begin Begin elisti.fromv:=1 elisti.fromv:=1；elisti.endv:=i+1elisti.endv:=i+1；elisti.weight:=g1,i+1elisti.weight:=g
8、1,i+1；EndEnd；求出最小生成树的求出最小生成树的n-1n-1条边；条边；For k:=1 To n-1 DoFor k:=1 To n-1 Do Begin Begin min:=maxint min:=maxint；m:=km:=k；For j:=k To n-1 Do For j:=k To n-1 Do 查找权值最小的一条边查找权值最小的一条边 If elistj.weightmin Then Begin min:=elistj.weight If elistj.weightmin Then Begin min:=elistj.weight；m:=jm:=j；EndEnd；If
9、 mk Then Begin t:=elistkIf mk Then Begin t:=elistk；elistk:=elistmelistk:=elistm；elistm:=telistm:=t；EndEnd；把权值最小的边调到第把权值最小的边调到第k k个单元个单元 j:=elistk.endv j:=elistk.endv；jj为新加入的顶点为新加入的顶点 For i:=k+1 To n-1 Do For i:=k+1 To n-1 Do 修改未加入的边集修改未加入的边集 Begin s:=elisti.endv Begin s:=elisti.endv；w:=gj,sw:=gj,s；I
10、f welisti.weight Then Begin elisti.weight:=wIf welisti.weight Then Begin elisti.weight:=w；elisti.fromv:=jelisti.fromv:=j；EndEnd；EndEnd；EndEnd；输输出；出；PrimPrim算法的实现算法的实现第7页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 2 2、用、用KruskalKruskal算法求最小生成树的思想如下：算法求最小生成树的思想如下：设设最小生成最小生成树为树为T=T=（V V，TETE），），设设置置边边的集合的集合TETE的初始状的初
11、始状态为态为空集。将空集。将图图G G中的中的边边按按权值权值从小到大从小到大排好序，然后从小的开始依次排好序，然后从小的开始依次选选取，若取，若选选取的取的边边使生成使生成树树T T不形成回路，不形成回路，则则把它并入把它并入TETE中，保留作中，保留作为为T T的一条的一条边边；若；若选选取的取的边边使生成使生成树树形成回路，形成回路，则则将其舍弃；如此将其舍弃；如此进进行下去，直到行下去，直到TETE中包含中包含n-1n-1条条边边为为止。最后的止。最后的T T即即为为最小生成最小生成树树。如何证明呢？如何证明呢？第8页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 Krusk
12、alKruskal算法在算法在实现过实现过程中的关程中的关键键和和难难点在于：如何判断欲加入的一条点在于：如何判断欲加入的一条边边是否与生成是否与生成树树中已保留的中已保留的边边形成回路？形成回路？我我们们可以将可以将顶顶点划分到不同的集合中，每个集合中的点划分到不同的集合中，每个集合中的顶顶点表示一个无回路的点表示一个无回路的连连通分量，很通分量，很明明显显算法开始算法开始时时，把所有，把所有n n个个顶顶点划分到点划分到n n个集合中，每个集合只有一个个集合中，每个集合只有一个顶顶点，表明点，表明顶顶点点之之间间互不相通。当互不相通。当选选取一条取一条边时边时，若它的两个，若它的两个顶顶点
13、分属于不同的集合，点分属于不同的集合，则则表明此表明此边连边连通通了两个不同的了两个不同的连连通分量，因每个通分量，因每个连连通分量无回路，所以通分量无回路，所以连连通后得到的通后得到的连连通分量仍不会通分量仍不会产产生回路，因此生回路，因此这这条条边应该边应该保留，且把它保留，且把它们们作作为为一个一个连连通分量，即把它的两个通分量，即把它的两个顶顶点所在集点所在集合合并成一个集合。如果合合并成一个集合。如果选选取的一条取的一条边边的两个的两个顶顶点属于同一个集合，点属于同一个集合，则则此此边应该边应该舍弃，舍弃，因因为为同一个集合中的同一个集合中的顶顶点是点是连连通无回路的，若再加入一条通
14、无回路的，若再加入一条边则边则必然必然产产生回路。生回路。就是并查集的思想。就是并查集的思想。第9页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 将图的存储结构转换成边集数组表示的形式将图的存储结构转换成边集数组表示的形式elistelist，并按照权值从小到大排好序；，并按照权值从小到大排好序；设数组设数组C1.n-1C1.n-1用来存储最小生成树的所有边，用来存储最小生成树的所有边，CiCi是第是第i i次选取的可行边在排好序的次选取的可行边在排好序的elistelist中的下标；中的下标；设一个数组设一个数组S1.nS1.n，SiSi都是集合，初始时都是集合，初始时Si=i
15、Si=i。i:=1i:=1；获取的第获取的第i i条最小生成树的边条最小生成树的边 j:=1 j:=1；边集数组的下标边集数组的下标 While i=n-1 Do While i=n-1 Do Begin Begin For k:=1 To n Do Begin For k:=1 To n Do Begin 取出第取出第j j条边，记下两个顶点分属的集合序号条边，记下两个顶点分属的集合序号 If elistj.fromv in sk Then m1:=k If elistj.fromv in sk Then m1:=k；If elistj.endv in sk Then m2:=kIf eli
16、stj.endv in sk Then m2:=k；EndEnd；If m1m2 Then Begin If m1m2 Then Begin 找到的找到的elistelist第第j j条边满足条件，作为第条边满足条件，作为第i i条边保留条边保留 Ci:=j Ci:=j；i:=i+1i:=i+1；sm1:=sm1+sm2sm1:=sm1+sm2；合并两个集合合并两个集合 sm2:=sm2:=；另一集合置空另一集合置空 End End；j:=j+1j:=j+1；取下条边，继续判断取下条边，继续判断 End End；输输出最小生成出最小生成树树的各的各边边：elistCielistCi Krusk
17、alKruskal算法的实现算法的实现第10页，本讲稿共11页最小生成树算法及应用最小生成树算法及应用 二、二、求图的最小生成树算法小结求图的最小生成树算法小结 都是基于贪心算法都是基于贪心算法时间复杂度均为时间复杂度均为O O（n*nn*n）PrimPrim算法和算法和KruskalKruskal算法算法三、应用举例三、应用举例例例2 2、最优布线问题（、最优布线问题（wire.?wire.?）学学校校有有n n台台计计算算机机，为为了了方方便便数数据据传传输输，现现要要将将它它们们用用数数据据线线连连接接起起来来。两两台台计计算算机机被被连连接接是是指指它它们们时时间间有有数数据据线线连连
18、接接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当当然然，如如果果将将任任意意两两台台计计算算机机都都用用数数据据线线连连接接，费费用用将将是是相相当当庞庞大大的的。为为了了节节省省费费用用，我我们们采采用用数数据据的的间间接接传传输输手手段段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。现在由你负责连
19、接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。输入格式输入格式 输入文件第一行为整数输入文件第一行为整数n n（2=n=1002=n=100），表示计算机的数目。此后的），表示计算机的数目。此后的n n行，每行行，每行n n个整数。个整数。第第x+1x+1行行y y列的整数表示直接连接第列的整数表示直接连接第x x台计算机和第台计算机和第y y台计算机的费用。台计算机的费用。输出格式输出格式 输出文件只有一个整数，表示最小的连接费用。输出文件只有一个整数，表示最小的连接费用。样例输入样例输入 样例输出样例输出 3 23 2（注：表示连接（注：表示连接1 1和和2 2，2 2和和3 3，费用为，费用为2 2）0 1 20 1 21 0 11 0 12 1 02 1 0第11页，本讲稿共11页