数据结构15--最小生成树

1、该图的最小生成树可以对该图执行深度优先搜索或者宽度优先搜索以生成单个深度优先搜索树或者宽度优先搜索树。 生成树的形态因检索的出发点而不同。 在一个权利连通图中，各边权利和最小的一个生成树为最小生成树。 修正最小生成树的思维方法：为了保证边的权重总和最小，必须形成(u，v )环，保证在保证的基础上尽量减小权重，并追加。 这种边称为安全边，有两个算法可以修正图的最小生成树、kruskal算法、prim算法。 早期，森林是由单一节点组成的n棵树。 计程仪列、kruskal普拉姆、const maxn=200； 最大值=最大值； 顶点数和边数的上限*/type edgetype=record /*边的

2、类型*/x，y，c :长度； 边权为c的边(x，y)*/end； vare :阵列1. maxeofedgetype /*边缘定径套。 第i个边缘为(ei.x，ei.y )，其边缘的权重为ei.c*/n，m，ans 3360长度； 顶点数为n，边数为m */f :阵列1.最大长度； /*并列调查。 其中，fi是顶点i存在的合并定径套的代表顶点，即通过子树的根*/，函数top(i )得到顶点i存在的子树的根，functop (i 3360 longint ) 3360 longint； /*修正顶点i所在的残奥级别定径套的代表顶点*/if ifi then fitop(fi )并返回。 如果不是

3、存在/*i的并行复选定径套的代表顶点，则沿着*/topfi； /*顶点i存在的残奥级定径套的代表顶点*/； 根据/*top*/，进程union(i，j，c )，合并顶点i和顶点j存在的2棵树，现有的边权是c的边(i，j )。 如果这边的2个端点属于2个树，顶点i和顶点j存在的子树的根分别是x和v，则加上(i，j )最小生成树，综合2个树(即顶点i和顶点j存在的和集合)。 /*i和j的集合*/var x，y 3360长度； xtop(i )； ytop(j )； /*分别取出顶点i和顶点j所在的子树的根*/if xy then inc(ans，c )。 fyx； 如果/*i和j属于两个子树，则该

4、边的权利被修正为最小生成树的权利和，两个子树为*/； /* union */，按边缘权重值(c结构域值)增加的顺序对主算法、边缘定径套e进行排序。 建立由包含/*图顶点*/ans0的n棵树构成的森林/*最小生成树的权重和初始化为0*/for i1 to m do union(ei.x、ei.y、ei.c )。 /*列出每条边，并将两个端点属于两个树的边添加到最小生成树*/writeln(ans )中。显然，kruskal算法的效率依赖于边数m，因此可应用平台即服务图。prim算法是集合a中的边总是形成单一的树，在每次追加树时尽可能减小树的权重的边。 设定、di顶点i与生成树连接的最短边的长度。 bai顶点i的生成树中的标志wi，j(i，j )的边的长度。 图中如果不存在边(i，j )，则wi，j=min的所有生成树中不存在的顶点的最小距离值，fillchar(ba，sizeof(ba )，0 )； 生成树*/for i2 to n do di中没有所有顶点。 /*所有顶点的距离值初始化*/d10； ans0； /*顶点1的距离值和生成树的权重和初始化*/for i1 to n do