1.prim普利姆算法

普里姆算法介绍

普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。

代码实现： 

import java.util.Arrays;

public class PrimAlgorithm {
    public static void main(String[] args) {

        char[] data = {'A','B','C','D','E','F','G'};
        int numNode= data.length;
        int[][] weight={
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };

        //创建一个MGraph对象
        MGraph graph=new MGraph(numNode);
        //创建一个MinTree对象
        MinTree minTree=new MinTree();
        //创建图
        minTree.createGraph(graph,numNode,data,weight);

        //显示图的邻接矩阵
        minTree.showGraph(graph);

        //测试prim算法
        minTree.prim(graph,0);
    }
}

//创建最小生成树
class MinTree{

    /**
     * 创建图
     * @param graph 图对象
     * @param numNode 图的顶点个数
     * @param data 图的各顶点值
     * @param weight 图邻接矩阵
     */
    public void createGraph(MGraph graph,int numNode,char[] data,int[][] weight){

        for (int i = 0; i < numNode; i++) {
            graph.data[i]=data[i];
            for (int j = 0; j < numNode; j++) {
                graph.weight[i][j]=weight[i][j];
            }
        }
    }

    //显示图的邻接矩阵
    public void showGraph(MGraph graph){

        for (int[] link:graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 编写一个prim算法，得到最小生成树
     * @param graph 传入的图
     * @param v 表示从图的第几个顶点开始生成 'A' -> 0 'B' -> 1
     */
    public void prim(MGraph graph,int v){

        //visited[]数组标记顶点是否被访问过，初始化为0，默认元素都没有被访问过
        int[] visited=new int[graph.numNode];
        visited[v]=1;

        int maxWeight=10000;
        //用h1和h2记录两个定点的下标
        int h1=-1;
        int h2=-1;

        for (int k = 1; k < graph.numNode; k++) {//有graph.numNode个顶点的话，生成graph.numNode - 1条边

            for (int i = 0; i < graph.numNode; i++) {//i节点：找到访问过的节点
                for (int j = 0; j < graph.numNode; j++) {//j节点：找到没有访问过的节点

                    if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<maxWeight){

                        //替换maxWeight
                        maxWeight=graph.weight[i][j];
                        //记录最后最小权值对应的两个顶点
                        h1=i;
                        h2=j;
                    }
                }
            }
            //此时h1和h2记录了一条最小的边
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + maxWeight);
            //将当前这个节点标记为已经访问过的节点
            visited[h2]=1;
            //maxWeight重置为10000
            maxWeight=10000;
        }
    }
}

//创建图 每一个MGraph对象表示一个图
class MGraph{

    int numNode;//表示图的节点个数
    char[] data;//存放节点数据
    int[][] weight;//存放边,也就是邻接矩阵

    public MGraph(int numNode) {
        this.numNode = numNode;
        data=new char[numNode];
        weight=new int[numNode][numNode];
    }
}

3.kruskal克鲁斯卡尔算法

1) 某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通

2) 各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里

3) 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?

也是求最小生成树

1) 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

2) 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路

3) 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

代码实现：

import java.util.Arrays;
import java.util.Comparator;

import static com.gou.kruskal.KruskalCase.INF;

public class KruskalCase {

    public static final  int INF=Integer.MAX_VALUE;

    public static char[] data = {'A','B','C','D','E','F','G'};
    public static int[][] weight ={
            {0,12,INF,INF,INF,16,14},
            {12,0,10,INF,INF,7,INF},
            {INF,10,0,3,5,6,INF},
            {INF,INF,3,0,4,INF,INF},
            {INF,INF,5,4,0,2,8},
            {16,7,6,INF,2,0,9},
            {14,INF,INF,INF,8,9,0}
    };

    public static int edgeNum;

    public static void main(String[] args) {

        //创建一个图对象
        Graph graph=new Graph(data.length);

        graph.data=data;
        graph.weight=weight;

        edgeNum = graph.getEdgeNum();

        kruskal();
    }

    //将边的数组按照权值大小进行排序
    public static void sortEData(EData[] edges){

        Arrays.sort(edges, new Comparator<EData>() {
            @Override
            public int compare(EData o1, EData o2) {
                return o1.weight-o2.weight;
            }
        });
    }

    //返回对应顶点的下标
    public static int getPosition(char ch){

        for (int i = 0; i < data.length; i++) {
            if (data[i]==ch){
                return i;
            }
        }
        //找不到
        return -1;
    }

    /**
     * 根据邻接矩阵获取图中的边的集合
     * EData[] 形式 [{'A','B',12},['B','F',7]...]
     * @return
     */
    public static EData[] getEdges(){

        EData[] edges=new EData[edgeNum];
        int index=0;

        for (int i = 0; i < data.length; i++) {
            for (int j = i+1; j < data.length; j++) {

                if (weight[i][j]!=INF){

                    edges[index]=new EData(data[i],data[j],weight[i][j]);
                    index++;
                }
            }
        }
        return edges;
    }

    /**
     * 功能:获取下标为i的顶点的终点(),用于后面判断两个顶点的终点是否相同
     * @param end 数组就是记录了各个顶点对应的终点是哪个,ends数组是在遍历过程中，逐步形成
     * @param i 表示传入的顶点对应的下标
     * @return 返回的就是下标为i的这个顶点对应的终点的下标
     */
    public static int getEnd(int[] end,int i){

        while (end[i]!=0){
            i=end[i];
        }
        return i;
    }

    public static void kruskal(){

        int index=0;//表示最后结果数组的索引

        int[] ends=new int[edgeNum];//用于保存"已有最小生成树"中的每个顶点在最小生成树中的终点

        //创建结果数组,保存最后的最小生成树
        EData[] res=new EData[edgeNum];

        //获取图中所有的边的集合
        EData[] edges = getEdges();

        //按照边的权值大小进行排序(从小到大)
        sortEData(edges);

        //遍历edges数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入rets,否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            //获取到第i条边的第一个顶点(起点)
            int p1 = getPosition(edges[i].start);
            //获取到第i条边的第2个顶点
            int p2 = getPosition(edges[i].end);

            //获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(ends, p1);
            //获取p2这个顶点在已有最小生成树中的终点
            int n = getEnd(ends, p2);

            //是否构成回路
            if (m!=n){
                ends[m]=n;
                res[index++]=edges[i];
            }
        }
        System.out.println("最小生成树为");
        for (int i = 0; i < index; i++) {
            System.out.println(res[i]);
        }
    }
}

class Graph{

    int edgeNum;//边的数量
    int nodeNum;//顶点数量
    char[] data;//顶点的数值
    int[][] weight;//邻接矩阵

    public Graph(int nodeNum) {
        this.nodeNum = nodeNum;
        data=new char[nodeNum];
        weight=new int[nodeNum][nodeNum];
        edgeNum=0;
    }

    //统计边的数量
    public int getEdgeNum(){

        for (int i = 0; i < data.length; i++) {
            for (int j = i+1; j < data.length; j++) {

                if (weight[i][j]!=INF){
                    edgeNum++;
                }
            }
        }
        return edgeNum;
    }

    //展示邻接矩阵
    public void showWeight(){

        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < weight[0].length; j++) {
                System.out.printf("%12d",weight[i][j]);
            }
            System.out.println();
        }
    }
}

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;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}