2023年8月1日发(作者：)
最⼩⽣成树——克鲁斯卡尔算法（Kruskal算法）克鲁斯卡尔算法(Kruskal算法)对于n个顶点的连通图⽽⾔，其⽣成的最⼩⽣成树有n-1条边，即可以保证从任⼀点出发可以到达任⼀点且不产⽣回路。克鲁斯卡尔算法(Kruskal算法)：对每条边的权值进⾏从⼩到⼤排序，然后从⼩到⼤取权值最⼩的边，如取出的边会在树中产⽣回路则舍去，取下⼀条；若不会产⽣回路则加⼊到树中。因此Kruskal算法的关键问题就是：如何判断新加⼊的边是否会产⽣回路。判断是否会产⽣回路的⽅法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否⼀致，如果⼀致，说明它们本⾝就处在⼀棵树中，如果继续连接就会产⽣回路；如果不⼀致，说明它们之间还没有任何关系，可以连接，同时连接后会将其顶点标记改变。变化过程以下图表⽰每个顶点标记状态的变化过程，两点颜⾊相同表⽰在同⼀边上，多点颜⾊相同表⽰在树上。实现⽅法：建⽴两个结构体数组，⼀个⽤于存储边的信息edge edges，⼀个⽤于记录各个点的标记assist assiststypedef struct edge{ VertexType initial; //起点 VertexType end;//终点 VertexType weight;//权值}edge[MAX_VERtEX_NUM];//定义辅助数组typedef struct { VertexType value;//顶点数据 int sign;//每个顶点所属的集合}assist[MAX_VERtEX_NUM];对edges进⾏升序排序，为⽅便观察⽤字母来表⽰起始点（实际存储的是int）。下⾯是edges（左）和 assists（右）的信息当AC构成⼀条边时，判断是否构成回路，因为AC的标记不同，所以成功。 信息C的标记就变为A的标记，同时AC这条边就相当于在树中存在了。下次就会从edges中的DF进⾏判断，更新两个数组的信息下次判断DF，成功，F的标记改为D的标记同样BECF，判断成功，注意这时不仅需要把F变为C的标记，同时F后⾯连接的所有是树中的点都要改为C的标记，本例中FD都要改变AD标记相同，不成功，判断BC，成功。⾄此⼀共产⽣5条边，对于6个顶点的最少⽣成树，已经找出了满⾜其条件的5条边了。总结：对于新的树中的边，把终点及其所连接的所有是树中点的标记改为起始点的标记如X——Y是新的边，x为起点，y为终点连接后各点标记会改为int main(){ int arcnum, vexnum; edge edges;//边信息的数组 CreateUDN(&edges, &vexnum, &arcnum); //对连通⽹中的所有边进⾏升序排序，结果仍保存在edges数组中
使⽤的是库函数 qsort(edges, arcnum, sizeof(edges[0]), cmp); //创建⼀个空的结构体数组，⽤于存放最⼩⽣成树 edge minTree; //设置⼀个⽤于记录最⼩⽣成树中边的数量的常量 int num = 0; //遍历所有的边 for (int i = 0; i
2023年8月1日发(作者：)
最⼩⽣成树——克鲁斯卡尔算法（Kruskal算法）克鲁斯卡尔算法(Kruskal算法)对于n个顶点的连通图⽽⾔，其⽣成的最⼩⽣成树有n-1条边，即可以保证从任⼀点出发可以到达任⼀点且不产⽣回路。克鲁斯卡尔算法(Kruskal算法)：对每条边的权值进⾏从⼩到⼤排序，然后从⼩到⼤取权值最⼩的边，如取出的边会在树中产⽣回路则舍去，取下⼀条；若不会产⽣回路则加⼊到树中。因此Kruskal算法的关键问题就是：如何判断新加⼊的边是否会产⽣回路。判断是否会产⽣回路的⽅法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否⼀致，如果⼀致，说明它们本⾝就处在⼀棵树中，如果继续连接就会产⽣回路；如果不⼀致，说明它们之间还没有任何关系，可以连接，同时连接后会将其顶点标记改变。变化过程以下图表⽰每个顶点标记状态的变化过程，两点颜⾊相同表⽰在同⼀边上，多点颜⾊相同表⽰在树上。实现⽅法：建⽴两个结构体数组，⼀个⽤于存储边的信息edge edges，⼀个⽤于记录各个点的标记assist assiststypedef struct edge{ VertexType initial; //起点 VertexType end;//终点 VertexType weight;//权值}edge[MAX_VERtEX_NUM];//定义辅助数组typedef struct { VertexType value;//顶点数据 int sign;//每个顶点所属的集合}assist[MAX_VERtEX_NUM];对edges进⾏升序排序，为⽅便观察⽤字母来表⽰起始点（实际存储的是int）。下⾯是edges（左）和 assists（右）的信息当AC构成⼀条边时，判断是否构成回路，因为AC的标记不同，所以成功。 信息C的标记就变为A的标记，同时AC这条边就相当于在树中存在了。下次就会从edges中的DF进⾏判断，更新两个数组的信息下次判断DF，成功，F的标记改为D的标记同样BECF，判断成功，注意这时不仅需要把F变为C的标记，同时F后⾯连接的所有是树中的点都要改为C的标记，本例中FD都要改变AD标记相同，不成功，判断BC，成功。⾄此⼀共产⽣5条边，对于6个顶点的最少⽣成树，已经找出了满⾜其条件的5条边了。总结：对于新的树中的边，把终点及其所连接的所有是树中点的标记改为起始点的标记如X——Y是新的边，x为起点，y为终点连接后各点标记会改为int main(){ int arcnum, vexnum; edge edges;//边信息的数组 CreateUDN(&edges, &vexnum, &arcnum); //对连通⽹中的所有边进⾏升序排序，结果仍保存在edges数组中
使⽤的是库函数 qsort(edges, arcnum, sizeof(edges[0]), cmp); //创建⼀个空的结构体数组，⽤于存放最⼩⽣成树 edge minTree; //设置⼀个⽤于记录最⼩⽣成树中边的数量的常量 int num = 0; //遍历所有的边 for (int i = 0; i
发布评论