第八章讲 贪心算法.ppt

此算法概括如下，它找出了最小生成树T的边集。 1. T ?{};X ?{1};Y ?V-{1} 2. While Y ≠{} 3. 设(x,y)是最小权重的边，其中x∈X，y∈Y 4. X ? X ∪{y} 5. Y ?Y-{y} 6. T ?T ∪{(x,y)} 7. End while PRIM算法的实现 假设输入用邻接表表示。边(x,y)的耗费(即权重)记为c[x,y]，存储在对应于x的邻接表中y的节点里。X和Y两个集合用布尔向量X[1…n]和Y[1…n]来实现。 初始时，X[1]=1, Y[1]=0,并且对所有i, 2≤i≤n, X[i]=0,Y[i]=1。这样，通过置X[y]为1来实行运算X?X∪{y},并且用置Y[y]为0来实现运算Y?Y-{y}。树的边集T用链表来实现，这样要实现运算T?T ∪{x,y}就简单地把边(x,y)添加到T中。 如果(x,y)是一条这样的边：x∈X,y∈Y，则称y为边界顶点，它是从Y移向X的候选顶点。设y为边界顶点，那么至少存在一个顶点x∈X与之邻接。 定义y的邻居(记为N[y])是X中具有以下性质的那个顶点x：在所有X中邻接于y的顶点中，c[x,y]最小。 我们又定义C[y]=c[y,N[y]]，因此N[y]是X中离y最近的邻居，并且C[y]是连接y和N[y]的边的耗费。此算法的描述在算法PRIM中给出。 算法8.4 PRIM INPUT:含权连通无向图G=(V,E),V={1,2,…,n} OUTPUT:由G生成的最小耗费生成树T组成的边的集合。 1. T ? { };X ? {1};Y ?V-{1} 2. for y ?2 to n 3. If y邻接于1 then 4. N[y] ?1 5. C[y] ?c[1,y] 6. Else C[y] ?∞ 7. End if 8. End for 9. For j ?1 to n-1 10. 令y∈Y，使得C[y]最小 11. T ?T∪{(y,N[y])}{将边(y,N[y])加入T} 12. X ?X∪{y} {将顶点y加入X} 13. Y ?Y-{y} {从Y中删除顶点y} 14. For 每个邻接于y的顶点w∈Y 15. If c[y,w]C[w] then 16. N[w] ?y 17. C[w] ?c[y,w] 18. End if 19. End for 20. End for 正确性 引理8.3 在含权连通无向图中，算法PRIM正确地找出最小耗费生成树。 证明：我们用对T的大小实施归纳法来证明，(X,T)是最小耗费生成树的子树。 初始时，T={}并且命题平凡地真。假设在算法的第11步添加边e=(x,y)之前命题为真，这里x∈X，y∈Y。设 ，我们将证明 也是某最小耗费生成树的子树。首先，我们证明 是一棵树，因为e 恰好与X中的一个称为x的顶点连接，同时根据归纳假设，(X,T)是一棵树， 是连通且无回路的，即是一棵树。 现在证明 是一颗最小耗费生成树的子树。根据归纳假设， ,这里T*是最小生成树 的边的集合。如果T*包含e，那么就不需要再进一步证明了。 否则，根据定理3.1(c ), T*∪{e}包含恰好一个以e为一条边的回路。因为e={x,y}连接了X中的一个顶点和Y中的另一个顶点， T*必定也包含另一条边 ，有w∈X, z∈Y。现在构造 ，注意到 并且，T**是最小生成树的边集，因为在所有连接X中顶点和Y中顶点的边中，e的值最小。 时间复杂性 此算法的时间复杂性计算如下。 第1步耗费?(n)时间，第2步的for循环需要时间?(n)，第3步到第6步需要时间O(n)。 第10步有哪些信誉好的足球投注网站离X最近