《算法设计与分析基础》（Python语言描述） 课件 第7章贪心法.pptx

第7章每一步局部最优—贪心法;7.1.1什么是贪心法;;;;;;;;;;;;;ej;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;1 INF=0x3f3f3f3f

2 defPrim(A,n,v): #Prim算法

3 T=[] #存放最小生成树

4 lowcost=[INF]*n

5 U=[0]*n

6 closest=[0]*n

7 forjinrange(0,n): #初始化lowcost和closest数组

8 lowcost[j]=A[v][j]

9 closest[j]=v

10 U[v]=1 #源点加入U;11 foriinrange(1,n): #找出(n-1)个顶点

12 mincost,k=INF,-1

13 forjinrange(0,n): #在(V-U)中找离U最近的顶点k

14 ifU[j]==0andlowcost[j]mincost:

15 mincost=lowcost[j]

16 k=j #k记录最近顶点的编号

17 T.append([closest[k],k,mincost]) #产生最小生成树的一条边

18 U[k]=1 #顶点k加入U

19 forjinrange(0,n): #修改数组lowcost和closest

20 ifU[j]==0andA[k][j]lowcost[j]:

21 lowcost[j]=A[k][j]

22 closest[j]=k

23 returnT;Prim算法是一种贪心算法，如何理解Prim算法的最优子结构性质呢？;采用反证法证明Prim算法满足最优子结构性质。

证明：如果采用Prim算法求出原问题的生成树T是最小生成树，选择第一条边(v，a)后得到相应的子问题，假设该子问题采用Prim算法求出的生成树T1（T=(v，a)∪T1）不是最小的，而是最小生成树为T2，则(v，a)∪T2得到原问题的一棵不同于T的更小的最小生成树，用T是原问题的最小生成树矛盾。最优子结构性质即证。;贪心选择性质证明。;;;当命题7.1成立时，k=n-1即选择了n-1条边，此时U包含G中所有顶点，由Prim算法构造的T=（U，TE）就是G的最小生成树。;7.3.2Kruskal算法构造最小生成树;;;首先，U中包含全部顶点，TE为空，看成是由n个连通分量构成的图，每个连通分量中只有一个顶点，当考虑一条边(u，v)时，若u和v属于两个不同的连通分量，则加入该边不会出现回路，否则会出现回路。这里每个连通分量就是并查集中的子集树。

用数组E存放图G中的所有边，按权值递增排序，再从头到尾依次考虑每一条边，若可以加入则选择该边作为最小生成树的一条边，否则舍弃该边。;#UFS并查集类参见第2章2.10.2节1～23的代码

1 INF=0x3f3f3f3f

2 defKruskal(A,n): #Kruskal算法

3 T=[] #存放最小生成树

4 E=[] #边集

5 foriinrange(0,n): #由A下三角部分产生的边集E

6 forjinrange(0,i):

7 ifA[i][j]!=0andA[i][j]!=INF:

8 E.append([i,j,A[i][j]])

9 E.sort(key=itemgetter(2)) #按边权值递增排序

10 ufs=UFS() #定义并查集对象

11 ufs.Init(n) #初始化并查集

12 k,j=0,0 #k表示当前构造生成树的边数;13 whilekn-1: #生成的边数小于n-1时循环

14 u1,v1=E[j][0],E[j][1] #取一条边(u1,v1)

15 sn1,sn2=ufs.Find(u1),ufs.Find(v1) #两个顶点所