2023年8月1日发(作者：)
彻底搞懂克鲁斯卡尔（Kruskal）算法（附C++代码实现）⼀.问题图中的6个顶点分别代表6个村庄，线段的权值代表村庄之间的距离。请问如何找到最短的路径来访问每⼀个村庄，且每个村庄只访问⼀次。⼆.解决1.提取图的边，并将边按权值⼤⼩从⼩到⼤排列，并放⼊edge数组。如下：
2.创建根数组（辅助数组），数组下标代表顶点节点本⾝，其元素代表顶点的根节点，如下：提⽰：这⾥的“根”并不是树结构中真正的根，⼀棵树中只有⼀个根，⽽这⾥的“根”泛指长辈，可能是⽗节点，也可能是“爷”节点。初始化根数组为-1，代表初始状态下每个顶点都各⾃代表⼀个集合。 3.将edge数组中的边从⼩到⼤依次放回图中，如果后续加⼊的边与图中已放⼊的边形成了环，那么将此边丢弃，继续将下⼀条边放⼊，规则同前。形成环，即说明加⼊的这条边的起点和终点已经属于⼀个集合，有共同的根。 加⼊边的过程就是多个⼦集不断合并的过程，同⼀集合中的顶点不可相连。前⾯的辅助数组就是⽤来判断起点与终点是否属于⼀个集合。具体实现看代码注释。 4.放⼊（顶点数-1）条边后，最⼩⽣成树（Minimum Spanning Tree）构建完成，即可结束循环。⼀棵树有n个节点，则有n-1条边三.细节
上述算法主要有两点需要考虑：树的储存集合的表⽰树的储存：常见的图储存结构有：邻接矩阵,邻接边表,⼗字链表,邻接多重表,边集数组 显然，上述算法中频繁涉及到对边的操作，所以边集数组是最佳选择。集合的表⽰：使⽤辅助数组，存放各顶点的根顶点，如果两个顶点的根相同，则属于同⼀集 合，另则相反。初始化辅助数组元素为-1，代表每个顶点本⾝就是根节点。四.实现
#include
for (int i = 0; i < vex; i++) roots[i] = -1; //初始化root数组，-1代表⾃⼰就是根节点；初始状态下每个顶点都是独⽴的根 for (int i = 0; i < MAX_EDGE; i++) { int vex_m = find_root(roots, gragh[i].start);//寻找起点的根节点 int vex_n = find_root(roots, gragh[i].end);//寻找终点的根节点 if (vex_m != vex_n)//如果两者的根节点不同，说明他们属于不同的集合，可以相连 { MST[count] = gragh[i];//将此边放⼊MST数组 count++; roots[vex_m] = vex_n;//将两个树合并，即将顶点vex_n作为vex_m的根节点 } if (count == vex-1)//当count达到顶点数-1，说明最⼩树已经⽣成，退出循环 break; } } for (int i = 0; i < vex - 1; i++) { printf("(%d,%d)%dn", MST[i].start, MST[i].end, MST[i].weight); //打印最⼩⽣成树 } return 0;}void ini_gragh(int& vex, int& edge, Edge* gragh){ cout << "输⼊连通⽹顶点数："; cin >> vex; cout << "输⼊连通⽹边数： "; cin >> edge; cout << "依次输⼊各边的起点，终点和权重(空格隔开)：" << endl; for (int i = 0; i < edge; i++) { cin >> gragh[i].start >> gragh[i].end >> gragh[i].weight; }}void sort_edge(Edge* edges_arr,int edge){ Edge temp;
for (int i = 0; i < edge; i++) { for (int k = 0; k < edge - i - 1; k++)//冒泡排序，注意这⾥要减1 { if (edges_arr[k].weight > edges_arr[k + 1].weight) { temp = edges_arr[k]; edges_arr[k] = edges_arr[k + 1]; edges_arr[k + 1] = temp; } } }}int find_root(int roots[], int n){ while (roots[n] > -1) //迭代寻找根节点 n = roots[n]; return n;}运⾏结果：
2023年8月1日发(作者：)
彻底搞懂克鲁斯卡尔（Kruskal）算法（附C++代码实现）⼀.问题图中的6个顶点分别代表6个村庄，线段的权值代表村庄之间的距离。请问如何找到最短的路径来访问每⼀个村庄，且每个村庄只访问⼀次。⼆.解决1.提取图的边，并将边按权值⼤⼩从⼩到⼤排列，并放⼊edge数组。如下：
2.创建根数组（辅助数组），数组下标代表顶点节点本⾝，其元素代表顶点的根节点，如下：提⽰：这⾥的“根”并不是树结构中真正的根，⼀棵树中只有⼀个根，⽽这⾥的“根”泛指长辈，可能是⽗节点，也可能是“爷”节点。初始化根数组为-1，代表初始状态下每个顶点都各⾃代表⼀个集合。 3.将edge数组中的边从⼩到⼤依次放回图中，如果后续加⼊的边与图中已放⼊的边形成了环，那么将此边丢弃，继续将下⼀条边放⼊，规则同前。形成环，即说明加⼊的这条边的起点和终点已经属于⼀个集合，有共同的根。 加⼊边的过程就是多个⼦集不断合并的过程，同⼀集合中的顶点不可相连。前⾯的辅助数组就是⽤来判断起点与终点是否属于⼀个集合。具体实现看代码注释。 4.放⼊（顶点数-1）条边后，最⼩⽣成树（Minimum Spanning Tree）构建完成，即可结束循环。⼀棵树有n个节点，则有n-1条边三.细节
上述算法主要有两点需要考虑：树的储存集合的表⽰树的储存：常见的图储存结构有：邻接矩阵,邻接边表,⼗字链表,邻接多重表,边集数组 显然，上述算法中频繁涉及到对边的操作，所以边集数组是最佳选择。集合的表⽰：使⽤辅助数组，存放各顶点的根顶点，如果两个顶点的根相同，则属于同⼀集 合，另则相反。初始化辅助数组元素为-1，代表每个顶点本⾝就是根节点。四.实现
#include
for (int i = 0; i < vex; i++) roots[i] = -1; //初始化root数组，-1代表⾃⼰就是根节点；初始状态下每个顶点都是独⽴的根 for (int i = 0; i < MAX_EDGE; i++) { int vex_m = find_root(roots, gragh[i].start);//寻找起点的根节点 int vex_n = find_root(roots, gragh[i].end);//寻找终点的根节点 if (vex_m != vex_n)//如果两者的根节点不同，说明他们属于不同的集合，可以相连 { MST[count] = gragh[i];//将此边放⼊MST数组 count++; roots[vex_m] = vex_n;//将两个树合并，即将顶点vex_n作为vex_m的根节点 } if (count == vex-1)//当count达到顶点数-1，说明最⼩树已经⽣成，退出循环 break; } } for (int i = 0; i < vex - 1; i++) { printf("(%d,%d)%dn", MST[i].start, MST[i].end, MST[i].weight); //打印最⼩⽣成树 } return 0;}void ini_gragh(int& vex, int& edge, Edge* gragh){ cout << "输⼊连通⽹顶点数："; cin >> vex; cout << "输⼊连通⽹边数： "; cin >> edge; cout << "依次输⼊各边的起点，终点和权重(空格隔开)：" << endl; for (int i = 0; i < edge; i++) { cin >> gragh[i].start >> gragh[i].end >> gragh[i].weight; }}void sort_edge(Edge* edges_arr,int edge){ Edge temp;
for (int i = 0; i < edge; i++) { for (int k = 0; k < edge - i - 1; k++)//冒泡排序，注意这⾥要减1 { if (edges_arr[k].weight > edges_arr[k + 1].weight) { temp = edges_arr[k]; edges_arr[k] = edges_arr[k + 1]; edges_arr[k + 1] = temp; } } }}int find_root(int roots[], int n){ while (roots[n] > -1) //迭代寻找根节点 n = roots[n]; return n;}运⾏结果：
发布评论