1 / 6 最小生成树算法分析一、生成树的概念若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs 或 dfs 后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs 或 bfs 亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs 或 dfs 后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。 要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用 bfs或 dfs ，这样得到的是生成森林。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。可以证明：具有n 个顶点的带权连通图，其对应的生成树有n-1 条边。二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V 和一部分边E’构成一个子图G’，即 G’=（V， E’），且边集 E’能将图中所有顶点连通又不形成回路，则称子图 G’是图 G的一棵生成树。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。2 / 6 例 1、城市公交网[ 问题描述 ] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。[ 输入 ] n（城市数， 1<=n<=100） e（边数）以下 e 行，每行 3 个数 i,j,wij ，表示在城市i,j之间修建高速公路的造价。[ 输出 ] n-1 行，每行为两个城市的序号，表明这两个城市间建一条高速公路。[ 举例 ] 下面的图（ A）表示一个5 个城市的地图，图（B）、（C）是对图（ A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20 和 33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。[ 问题分析 ] 出发点：具有n 个顶点的带权连通图，其对应的生成树有n-1 条边。那么选哪n-1 条边呢？设图 G的度为 n，...
VIP
