最小生成树(Kruskal)-

前言: 当初学数据结构的时候，听到这个名字被唬住了，认为晦涩难懂；其实不然，在理解和掌握并查集后，再看最小生成树，无非就是比并查集多了一个加权边的条件，其它基本相同。在学习之前，我们首先要知道最小生成树是个什么东西，我理解的最小生成树就是保证图上所有的点只有一个祖先且不出现回路用N-1（N为点的个数） 条边连在一起的图。这类题目可以利用Kruskal或Prim算法解决，这次我记录的是Kruskal算法。

基本原理:

先把所有边“去掉”，把所有点看成独立的；从最小的边权开始连，如果连接后不出现回路，则这次连接为有效连接，否则继续遍历，直到找到N-1次有效连接，则找到最小生成树。

基本步骤：

准备工作:

1.存储边，及其边权，可以用结构体存储(C++)也可以用类存储(Java)或者用邻接矩阵。(我选择的是类存储,用list容器保存)

2.根据边权进行排序

3.写出并查集find和union方法，并初始化祖先parent数组

开始Kruskal:

1.遍历已经排好序的结构体或list

2.输出最小边权总和

例题印证:

本例题来自(HDU_OJ)

Title

还是畅通工程

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

Sample Output

3
5

这道题是一道标准的最小生成树题目

AC Code：

import java.util.*;

public class Main {
    //并查集的code
    public static int find(int[] parent,int x){
        int r = x;
        while (parent[r]!=-1) {
            r = parent[r];
        }
        int j = x,i;
        while (j != r) {
            i = parent[j];
            parent[j] = r;
            j = i;
        }
        return r;
    }

    public static void union(int[] parent,int x,int y){
        if (x != y) {
            parent[x] = y;
        }
    }
    //Kruskal核心代码块
    public static int Kruskal(int[] parent,List<Edge> edges,int n){
        int sum = 0;
        for (Edge edge:edges){
            if (n == 0) {
                return sum;
            }
            int t1 = find(parent,edge.getFrom());
            int t2 = find(parent,edge.getTo());
            if (t1 != t2) {
                sum+=edge.getDis();
                n--;
                union(parent,t1,t2);
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //村庄数目
        int N = sc.nextInt();
        while (N != 0) {
            int[] parent = new int[N+1];
            //初始化map
            for (int i = 0 ; i <= N ;i++){
                parent[i] = -1;
            }

            //还要输入的行数
            int n = (N*(N-1))/2;
            List<Edge> edges = new ArrayList<Edge>();

            for (int j = 0 ; j < n;j++){
                int from = sc.nextInt();
                int to = sc.nextInt();
                int dis = sc.nextInt();
                edges.add(new Edge(from,to,dis));
            }
            //按边的权重排序
            Collections.sort(edges);

            System.out.println(Kruskal(parent,edges,N-1));

            N = sc.nextInt();
        }
    }
}
//把边和边的关系和边权存入Edge中
class Edge implements Comparable<Edge>{
    int from;
    int to;
    int dis;

    public Edge(int from, int to, int dis) {
        this.from = from;
        this.to = to;
        this.dis = dis;
    }

    public int getDis() {
        return dis;
    }

    public void setDis(int dis) {
        this.dis = dis;
    }

    public int getFrom() {
        return from;
    }

    public void setFrom(int from) {
        this.from = from;
    }

    public int getTo() {
        return to;
    }

    public void setTo(int to) {
        this.to = to;
    }
    //这个地方继承Comparable接口是为了一会的根据边权排序的工作，具体排序方法可以看之前一篇Blog
    @Override
    public int compareTo(Edge o) {
        return new Integer( this.getDis()).compareTo(o.getDis());
    }
}

「真诚赞赏，手留余香」

最小生成树(Kruskal)

TOC

基本原理:

基本步骤：

例题印证:

AC Code：

FEATURED TAGS

FRIENDS