历柴毛子代枚大学 最小生成树 XIDIAN UNIVERSITY 4.Prim算法（加点法) G=(V,E)为一图，其中V为顶点的集合，E为边的集合 第一步：从某一顶点1出发，选择与它相连的具有最小权值的边(1， ),将其顶点加入到生成树顶点集合U中。U用于存放G的最小 生成树中的顶点，F存放G的最小生成树中的边。初始时刻： U={v1};F={}。 第二步：重复上述步骤 以后每一步从U中选择一个顶点而另一个顶点属于V-U的边中 ,选取具有最小权值的边(，y),将顶点加入集合U中，将 边(，y)加入集合F中； 如此不断重复，直到U=V时，最小生成树构造完毕，这时集合F中 包含了最小生成树的所有边。 4. Prim算法（加点法） G=(V,E)为一图，其中V为顶点的集合，E为边的集合 第一步：从某一顶点v1出发，选择与它相连的具有最小权值的边(v1, vi)，将其顶点vi加入到生成树顶点集合U中。U用于存放G的最小 生成树中的顶点，F存放G的最小生成树中的边。初始时刻： U={v1} ；F={ }。 第二步：重复上述步骤 以后每一步从U中选择一个顶点vi, 而另一个顶点vj属于V-U的边中 ，选取具有最小权值的边（vi ， vj ），将顶点vj加入集合U中，将 边（ vi ，vj ）加入集合F中; 如此不断重复，直到U=V时，最小生成树构造完毕，这时集合F中 包含了最小生成树的所有边。 最小生成树 7