信息学奥赛一本通最小生成树(C 版)PPT讲座.ppt

引入一、什么是图的最小生成树(MST)? 不知道大家还记不记得树的一个定理:N个点用N-1条边连接成一个连通块,形成的图形只可能是树,没有别的可能。一个有N个点的图,边一定是大于等于N-1条的。图的最小生成树,就是在这些边中选择N-1条出来,连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。引入二、最小生成树用来解决什么问题? 就是用来解决如何用最小的“代价”用N-1条边连接N个点的问题。例如:【例4-9】、城市公交网建设问题【问题描述】有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?【输入格式】n(城市数,1<=n<=100) e(边数) 以下e行,每行3个数i,j,wij,表示在城市i,j之间修建高速公路的造价。【输出格式】 n-1行,每行为两个城市的序号,表明这两个城市间建一条高速公路。引入【输入样例】 58 122 259 547 4110 1312 436 533 238【输出样例】 12 23 34 35Prim算法Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想:白点代表已经进入最小生成树的点,蓝点代表未进入最小生成树的点。算法描述:以1为起点生成最小生成树,min[v]表示蓝点v与白点相连的最小边权。MST表示最小生成树的权值之和。a)初始化:min[v]=∞(v≠1);min[1]=0;MST=0;b)for(i=1;i<=n;i++)[u]最小的蓝点u。+=min[u](w[u][v]<min[v])min[v]=w[u][v];c)算法结束:MST即为最小生成树的权值之和算法分析&思想讲解:Prim算法每次循环都将一个蓝点u变为白点,并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边,最后得到的一定是最小生成树。我们通过对下图最小生成树的求解模拟来理解上面的思想。蓝点和虚线代表未进入最小生成树的点、边;白点和实线代表已进入最小生成树的点、边。Prim算法初始时所有点都是蓝点,min[1]=0,min[2、3、4、5]=∞。权值之和MST=0。123452471162第一次循环自然是找到min[1]=0最小的蓝点1。将1变为白点,接着枚举与1相连的所有蓝点2、3、4,修改它们与白点相连的最小边权。123452471162min[2]=w[1][2]=2;min[3]=w[1][3]=4;min[4]=w[1][4]=7;Prim算法第二次循环是找到min[2]最小的蓝点2。将2变为白点,接着枚举与2相连的所有蓝点3、5,修改它们与白点相连的最小边权。123452471162min[3]=w[2][3]=1;min[5]=w[2][5]=2;第三次循环是找到min[3]最小的蓝点3。将3变为白点,接着枚举与3相连的所有蓝点4、5,修改它们与白点相连的最小边权。123452471162min[4]=w[3][4]=1;由于min[5]=2<w[3][5]=6;所以不修改min[5]的值。Prim算法最后两轮循环将点4、5以及边w[2][5],w[3][4]添加进最小生成树。123452471162最后权值之和MST=6。这n次循环,每次循环我们都能让一个新的点加入生成树,n次循环就能把所有点囊括到其中;每次循环我们都能让一条新的边加入生成树,n-1次循环就能生成一棵含有n个点的树;每次循环我们都取一条最小的边加入生成树,n-1次循环结束后,我们得到的就是一棵最小的生成树。这就是Prim采取贪心法生成一棵最小生成树的原理。算法时间复杂度:O(N2)。Prim算法【例4-10】、最优布线问题()【问题描述】学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。【输入格式】,第一行为整数n(2<=n<=100),表示计算机的数目。此后的n行,每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费