数据结构与算法(Java版)第5章 图结构.ppt

* 5.4.2 最小生成树 下图 (a(b)和(c)所示的均为无向连通图G5的生成树 1 最小生成树的概念 * 2如何找到一个连通网络的最小生成树 (1) MST性质 MST性质设G(Vn, En)是一个连通网络U是顶点集Vn的一个真子集若(uv)是G中所有的一个端点在U即uU而另一个端点不在U即vVnU里的边中具有最小权值的一条边则一定存在G的一棵最小生成树包括此边(uv) * 5.4.3 构造