吉林大学数据结构_最小支撑树.pptx

最小支撑树;;对于一个无向网络——无向加权连通图N = (V, E, C)（C表示该图为权图），其顶点个数为|V| = n，图中边的个数为|E| ，我们可以从它的|E|条边中选出n-1条边，使之满足以下条件： 1) 这n-1条边和图的n个顶点构成一个连通图。 2) 该连通图是所有满足条件(1)且具有最小代价的连通图。 这样的连通图被称为网络N的最小支撑树。显然，一个网络可能存在不只一棵最小支撑树。 ;?;;普里姆 ( Prim ) 算法;?;克鲁斯卡尔 ( Kruskal ) 算法;设连通图N = (V, E, C)，T为N的最小支撑树。初始时，T={V, ?} ，即T中没有边，只有n个顶点，显然，这n个顶点就是n个连通分量。克鲁斯卡尔算法的基本步骤如下： 1) 在E中选择权值最小的边，并将此边从E中删除； 2) 如果此边的两个顶点在T的不同的连通分量中，则将此边加入到T中，从而导致T中减少一个连通分量； 3) 重复执行(1)、(2)，直至T中仅剩一个???通分量。