搜索

最小生成树——数据结构与算法学习


发布时间: 2022-11-24 18:42:00    浏览次数:31 次

最小生成树

普利姆算法

算法思想

如果从A点出发,则先比较A-G;A-B;A-C,从而选择最小的点为G点,因此将AG作为生成树

再依次比较距离AG生成树距离最小的顶点,从而加入生成树种,这里选择的就是AGB

普利姆算法图解

核心代码

——prim最小生成树构建

 for (int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs 顶点,普利姆算法结束后,有 graph.verxs-1 边
            for (int i = 0; i < graph.verxs; i++) {
                for (int j = 0; j < graph.verxs; j++) {
                    if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < min){
                        min = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }

——如果只需要找到节点,则使用一个lowcost数组,每次循环更新就可以减少算法复杂度

for (int i = 0; i < graph.verxs - 1; i++) {//针对每一个子树,遍历节点
            min = 10000;
            for (int j = 0; j < graph.verxs; j++) {//遍历未访问节点
                if(visited[j] == 0 && lowcost[j] < min){
                    min = lowcost[j];
                    h1 = j;
                    h2 = i;
                }
            }
            System.out.println("加入的节点为"+ graph.data[h1] + "> 权值:" + min);
            visited[h1] = 1;
            sum += min;
            v = h1;
            for (int j = 0; j < graph.verxs; j++) {//更新一个v对应的lowcost数组
                if(visited[j] == 0 && graph.weight[v][j] < lowcost[j]){//重新更新的条件
                    lowcost[j] = graph.weight[v][j];
                }
            }

克鲁斯卡尔算法

——在prim算法的思想上引入了边的思想

主要思想:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。

这里引入一个边的思想(这里就体现出自定义数据结构的妙用了)

class EData {
char start; //边的一个点
char end; //边的另外一个点
int weight; //边的权值
//构造器
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
//重写 toString, 便于输出边信息
@Override
public String toString() {
return "EData [<" + start + ", " + end + ">= " + weight + "]";
}
}

判断是否构成回路:就是寻找到待连接的两个顶点的终点是否相同,其实就是子树的根节点是否相同。

private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
while(ends[i] != 0) {
i = ends[i];//寻找到根节点
}
return i;
}
免责声明 最小生成树——数据结构与算法学习,资源类别:文本, 浏览次数:31 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:42:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/robyn2022/p/16915706.html