最小生成树算法详解PPT优秀课件

1、最小生成树算法 -prim double lowcost; closedgeMAX_VERTEX_NUM; closedgei.adjvex=k closedgei.lowcost 顶点i与顶点k邻接 顶点k已经在U集合中 顶点i加入U集合时 = 0 15 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 v2v3v4v5v6UV-Uk 顶点i closedge closedge2.adjvex=1 .lowcost=6 closedge3.adjvex=1 .lowcost=1 closedge4.adjvex=1 .lowcost=5 V

2、4 V1 V3 V2 V6V5 1 65 F当当U U集合中加入一个新顶点时，集合中加入一个新顶点时，V-UV-U集合中的顶点到集合中的顶点到U U 的最小代价边可能会更新的最小代价边可能会更新 V4 V1 V3 V2 V6V5 6 5 1 2 6 6 5 5 3 4 U集合的成员： V-U集合的成员： closedge5.adjvex=1 .lowcost= closedge6.adjvex=1 .lowcost= 16 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 adjvex lowcost v3 5 0 v1 5 v3 6 v3

3、4 v1,v3v2,v4,v5,v6 6 v2v3v4v5v6UV-Uk 顶点i closedge V4 V1 V3 V2 V6V5 5 5 64 U集合的成员： V-U集合的成员： F当当U U集合中加入一个新顶点时，集合中加入一个新顶点时，V-UV-U集合中的顶点到集合中的顶点到U U 的最小代价边可能会更新的最小代价边可能会更新 V4 V1 V3 V2 V6V5 6 5 1 2 6 6 5 5 3 4 closedge2.adjvex=3 .lowcost=5 closedge4.adjvex=1 .lowcost=5 closedge5.adjvex=3 .lowcost=6 clos

4、edge6.adjvex=3 .lowcost=4 17 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 adjvex lowcost v3 5 0 v1 5 v3 6 v3 4 v1,v3v2,v4,v5,v66 adjvex lowcost v3 5 0 v6 2 v3 6 0v1,v3,v6v2,v4,v5 4 v2v3v4v5v6UV-Uk 顶点i closedge V4 V1 V3 V2 V6V5 5 6 2 V4 V1 V3 V2 V6V5 6 5 1 2 6 6 5 5 3 4 F当U集合中加入一个新顶点时，V-U集合中的顶点

5、到 U的最小代价边可能会更新 U集合的成员： V-U集合的成员： closedge2.adjvex=3 .lowcost=5 closedge4.adjvex=6 .lowcost=2 closedge5.adjvex=3 .lowcost=6 18 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 adjvex lowcost v3 5 0 v1 5 v3 6 v3 4 v1,v3v2,v4,v5,v66 adjvex lowcost v3 5 0 v6 2 v3 6 0v1,v3,v6v2,v4,v5 4 adjvex lowcost v

6、3 5 00 v3 6 0v1,v3,v6,v4v2,v5 v2v3v4v5v6UV-Uk 顶点i closedge 2 V4 V1 V3 V2 V6V5 5 6 F当U集合中加入一个新顶点时，V-U集合中的顶点到 U的最小代价边可能会更新 U集合的成员： V-U集合的成员： V4 V1 V3 V2 V6V5 6 5 1 2 6 6 5 5 3 4 closedge2.adjvex=3 .lowcost=5 closedge5.adjvex=3 .lowcost=6 19 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 adjvex low

7、cost v3 5 0 v1 5 v3 6 v3 4 v1,v3v2,v4,v5,v66 adjvex lowcost v3 5 0 v6 2 v3 6 0v1,v3,v6v2,v4,v5 4 adjvex lowcost v3 5 00 v3 6 0v1,v3,v6,v4v2,v5 2 adjvex lowcost 000 v2 3 0v1,v3,v6,v4,v2v5 v2v3v4v5v6UV-Uk 顶点i closedge 5 V4 V1 V3 V2 V6V5 3 F当U集合中加入一个新顶点时，V-U集合中的顶点到 U的最小代价边可能会更新 V4 V1 V3 V2 V6V5 6 5 1 2

8、 6 6 5 5 3 4 U集合的成员： V-U集合的成员： 20 adjvex lowcost v1 6 v1 1 v1 5 v1 v2,v3,v4,v5, v6 3 adjvex lowcost v3 5 0 v1 5 v3 6 v3 4 v1,v3v2,v4,v5,v66 adjvex lowcost v3 5 0 v6 2 v3 6 0v1,v3,v6v2,v4,v5 4 adjvex lowcost v3 5 00 v3 6 0v1,v3,v6,v4v2,v5 2 v2v3v4v5v6UV-Uk 顶点i closedge V4 V1 V3 V2 V6V5 adjvex lowcost

9、 00000 v1,v3,v6,v4,v2,v 5 adjvex lowcost 000 v2 3 0v1,v3,v6,v4,v2v5 5 1 4 2 5 3 U集合的成员： V-U集合的成员： V4 V1 V3 V2 V6V5 6 5 1 2 6 6 5 5 3 4 21 图采用邻接矩阵表示 普里姆算法求最小生成树普里姆算法求最小生成树 6 1 5 6 5 3 1 5 5 6 4 5 5 2 3 6 6 4 2 6 1 2 3 4 5 6 1 2 3 4 5 6 graph. arac = #include #include #include #define INIT 63355 #defi

10、ne NUM 20 using namespace std; typedef int Elemtype; typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e; graph; void Init_Graph(graph i=g.v;i+) for(int j = 1;j=g.v;j+) g.aracij = INIT; void Create_Graph(graph Init_Graph(g); cout输入顶点信息:endl; for(int i = 1;ig.vexi; cout输入顶点间下标和权 值:endl; int

11、 k,t,w; for(int i = 1;iktw; g.arackt = w; g.aractk = g.arackt; void Prim(graph int lowcostNUM; /当前最短距离 int closestNUM; /顶点的相邻顶点 (closesti则为i的邻接点) int sNUM; /标志访问节点 for(int i = 1;i=g.v;i+) closesti = 1; /初始置各顶 点得邻接点为1 lowcosti = g.arac1i; /初始置各顶 点的最短距离为1到顶点的距离 si = 0; for(int i = 1;ig.v;i+) int min =

12、 INIT; /min初始化无 穷大 int j = 1; for(int k = 2;k=g.v;k+) if(lowcostkmin j = k; min_cost+=min; coutclosestjjendl; /输出符合最小生成 树的顶点 sj = 1; /已访问顶点置1 for(int t = 2;t=g.v;t+) if(g.aracjtlowcostt closestt = j; cout最小生成树得最短路径 为:min_costendl; KruskalKruskal最小生成树 KruskalKruskal算法步骤：算法步骤： 56 42 3 1 1 6 5 34 6 5 2

13、 6 5 a.带权图 此算法可以称为“加边法”，初始最小生成树边数 为0，每迭代一次就选择一条满足条件的最小代价 边，加入到最小生成树的边集合里。 1. 把图中的所有边按代价（权值）从小到大排 序； 2.将图中的所有边都去掉。 3.将边按权值从小到大的顺序添加到图中，保证添 加的过程中不会形成环 （用并查集检测 ） 4. 重复(3),直到所有顶点都在一颗树内或者有n-1 条边为止。 25 1 KruskalKruskal最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 26

14、 1 经典应用最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 27 1 经典应用最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 28 1 经典应用最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 29 1 经典应用最小生成树 5

15、5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 34这条边（蓝色表示）加入会形成环，所以这 条边不能用 30 1 经典应用最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5 2 6 5 14这条边（蓝色表示）加入会形成环，所以这 条边不能用 31 1 经典应用最小生成树 5 5、算法过程示意：、算法过程示意： 56 42 3 1 1 6 5 34 6 5 2 6 5 原始图 56 42 3 1 6 5 34 6 5