Kruskal算法说明及图解

1 无向网图及边集数组存储示意图无向网图及边集数组存储示意图 vertex 6 2 Kruskal 方法构造最小生成树的过程方法构造最小生成树的过程 a 一个图 b 最小生成树过程 1 V0V1V2V3V4V5 下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to 4 3 5 5 5 5 1 4 2 weight 12 17 19 25 25 26 34 38 46 V1 V0V4 V5 V2 V3 V1 V0 V5 V2V3 V4 c 最小生成树过程 2 d 最小生成树过程 3 e 最小生成树过程 4 c 最小生成树过程 5 3 伪代码伪代码 1 初始化辅助数组 初始化辅助数组 parent vertexNum num 0 2 依次考查每一条边依次考查每一条边 for i 0 i arcNum i vex1 edge i form 所在生成树的根结点所在生成树的根结点 vex2 edge i to 所在生成树的根结点所在生成树的根结点 If vex1 vex2 parent vex2 vex1 num if num vertexNum 1 算法结束算法结束 4 构造过程中参数变化构造过程中参数变化 顶点集顶点集 数组数组 parent V0V1V2V3V4V5被考查边被考查边输出输出说明说明 初始化初始化 parent 1 1 1 1 1 16 棵生成树 均只有根结点棵生成树 均只有根结点 parent 1 1 1 11 1 v1 v4 12 v1 v4 12vex1 1 vex2 4 parent 4 1 parent 1 1 121 1 v2 v3 17 v2 v3 17vex1 2 vex2 3 parent 3 2 parent 1 1 1210 v0 v5 19 v0 v5 19vex1 0 vex2 5 parent 5 0 parent2 1 1210 v2 v5 25 v2 v5 25vex1 2 vex2 0 parent 0 2 parent2 1 1210 v3 v5 25vex1 2 vex2 2 所在根结点相同所在根结点相同 parent2 11210 v4 v6 26 v4 v6 26vex1 1 vex2 2 parent 2 1 parent2 11210生成树根结点是生成树根结点是 v1 5 主要代码主要代码 构造函数构造函数 template EdgeGraph EdgeGraph DataType a int n int e vertexNum n edgeNum e int i j weight for int k 0 k vertexNum k vertex k a k for k 0 k edgeNum k cout i j edge k from i edge k to j cout weight edge k weight weight Kruskal 算法构造最小生成树算法构造最小生成树 template void EdgeGraph Kruskal int num int parent MaxVertex vex1 vex2 for int i 0 i vertexNum i parent i 1 for i 0 num 0 i edgeNum i vex1 FindRoot parent edge i from vex2 FindRoot parent edge i to if vex1 vex2 cout edge i from edge i to weight edge i weight endl parent vex2 vex1 num if num vertexNum 1 return 寻找根节点寻找根节点 template int EdgeGraph FindRoot int parent int v int t v while parent t 1 t parent t return t 遍历输出遍历输出 template void EdgeGraph Print for int i 0 i edgeNum i cout edge i from edge i to weight edge i weight endl 6 结果截图结果截图 发现不按大小输入发现不按大小输入 weight 的值则不能正确生成最小生成树的值则不能正确生成最小生成树 如如 排好序输入时则得到正确的最小生成树排好序输入时则得到正确的最小生成树 结果正确 所以需要按大小顺序输入权值大小的结果正确 所以需要按大小顺序输入权值大小的 Kr