java kruskal怎么实现最小生成树

Kruskal算法介绍

Kruskal算法是一种用于求解最小生成树的算法，它是由Joseph Kruskal在1956年提出的，它是一种贪心算法，它的基本思想是从一个图中选择n-1条边，使得这n-1条边构成的树的权值最小。Kruskal算法每次从图中选取最小权值的边加入到最小生成树中，直到所有的顶点都在同一颗树中。

Kruskal算法实现步骤

1、首先将所有的边按照权值从小到大的顺序排列。
2、从最小权值的边开始，依次考察每条边，如果该边连接的两个顶点不在同一个连通分量中，则将该边加入到最小生成树中，否则忽略该边。
3、重复步骤2，直到最小生成树中包含了图中所有的顶点。

Kruskal算法的Java实现

//定义边的结构体

class Edge{

    int start;

    int end;

    int weight;

}



//定义图的结构体

class Graph{

    int n; //顶点数

    int e; //边数

    Edge[] edges; //边数组

}



//Kruskal算法的实现

public static void Kruskal(Graph graph){

    int[] parent = new int[graph.n]; //定义一个数组来存储每个顶点的父节点

    for(int i=0;i<graph.n;i++){

        parent[i] = i; //初始化每个顶点的父节点为自身

    }

    //将边按权值从小到大排列

    Arrays.sort(graph.edges, new Comparator<Edge>(){

        public int compare(Edge e1, Edge e2){

            return e1.weight - e2.weight;

        }

    });

    //遍历每条边

    for(int i=0;i<graph.e;i++){

        Edge edge = graph.edges[i];

        int s = edge.start;

        int e = edge.end;

        //查找顶点s,e的父节点

        int ps = find(parent,s);

        int pe = find(parent,e);

        //如果s,e的父节点不同，则将s,e的父节点设置为同一个，并将该边加入到最小生成树中

        if(ps != pe){

            parent[ps] = pe;

            System.out.println(s + "-" + e);

        }

    }

}



//查找顶点的父节点

public static int find(int[] parent, int x){

    if(parent == x){

        return x;

    }

    return find(parent,parent);

}