Java实现最小生成树(Prim，Kruskal)

Prim算法的构建生成树的下一步都是在原树的基础上，每一步构成的生成树一定是一个连。算法的思路就是将当前的生成树看成一个整体，寻找距离这个整体最近的一个点P，将其加入生成树后，更新 l o w C o s t [ i ] lowCost[i] lowCost[i]数组，其中 c o s t [ i ] cost[i] cost[i]保存着当前生成树距离i点的最小距离

并记录已经加入生成树的点

for(int i=0;i 
第二步遍历寻找距离当前生成树最小的点 
for(int j=1;j lowCost[j] && find[j] != 1)
    {
        minCost = lowCost[j];
        index = j;//记录一下下标
    }
}
 
第三步是更新lowCost[i]数组 
for(int k=1;k 
Kruskal 
这个算法的思路是每次寻找图中权值最小的边，判断将边加入会不会构成环。如果不能，就加入，最多加入N-1条边（假设有N个点）
 根据图的性质，将N个点连接到一起变成连通图最小需要N-1条边，而且图中不存在环，因为我们求最小生成树，那么就找N-1条边就好
 
第一步初始化边集数组 
因为我们要有一个集合来存放边，边的元素有始点，终点，权值。因为要比较权值的大小，所以实现了Comparable接口的方法
 
class Edge implements Comparable {
    //起始点
    private int begin;
    //终止点
    private int end;
    //权值
    private int weight;

    public Edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }

    public int getBegin() {
        return begin;
    }

    public void setBegin(int begin) {
        this.begin = begin;
    }

    public int getEnd() {
        return end;
    }

    public void setEnd(int end) {
        this.end = end;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        if (o.weight > this.weight) {
            return -1;
        } else {
            return 1;
        }
    }
}
 
第二步判断是否能构成环 
这里采用了并查集的想法。假设每一个点都有自己的父节点，那么当一条边加入进生成树的时候，这条边始点和终点就有相同的父节点，如果成了环，那么肯定会有相同的父节点。
 
private static int find(int[] parent, int x) {
    while(x != parent[x])
    {
        x = parent[x];
    }
    return x;
}
 
第三步排序好，开始遍历 
从最小值出发，如果父节点不同就加入，直到边的数量为N-1
 
 m = find(parent, list.get(i).getBegin());
 n = find(parent, list.get(i).getEnd());
 if (m != n) {
     parent[m] = n;
     sum += list.get(i).getWeight();
     num++;
 }
 if(num == N-1)
     break;
 
完整代码
 题目链接