第四课时最小生成树
上一节
下一节
掌握建立最小生成树的两种方法
6.4.1 无向图的连通分量和生成树 若图是连通的或强连通的,则从图中某一个顶点出发可以访问到图中所有顶点; 若图是非连通的或非强连通图,则需从图中多个顶点出发搜索访问而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。 生成树:是一个极小连通子图,它含有图中全部顶点,但只有n-1条边。 6.4.2.生成森林 若一个图是非连通图或非强连通图,但有若干个连通分量或若干个强连通分量,则通过深度优先搜索遍历或广度优先搜索遍历,不可以得到生成树,但可以得到生成森林,且若非连通图有 n 个顶点,m 个连通分量或强连通分量,则可以遍历得到m棵生成树,合起来为生成森林,森林中包含n-m条树边。 6.4.3 最小生成树 构造最小生成树的准则 v 必须只使用该网络中的边来构造最小生成树; v 必须使用且仅使用n-1条边来联结网络中的n个顶点; v 不能使用产生回路的边。 ¬ 普里姆算法 ¬ 克鲁斯卡尔(kruskal)算法 1. 克鲁斯卡尔算法基本思想 将图中所有边按权值递增顺序排列,依次选定取权值较小的边,但要求后面选取的边不能与前面选取的边构成回路,若构成回路,则放弃该条边,再去选后面权值较大的边,n个顶点的图中,选够n-1条边即可。 |