贪心算法：Dijkstra最短路径，Prim最小生成树，Kruskal最小生成树（Java实现）

因为这学期上算法课，因为要准备蓝桥杯国赛，所以复习记录一下几个经典的算法 （T_T）。。。

贪心算法

1.Dijkstra最短路径

import java.util.ArrayList;
import java.util.HashMap;

/**
 *  @author: cuttle
 *  @Date: 2020/11/4 19:34
 *  @Description: 最短路径的Dijkstra算法，贪心法
 */
public class NS_DijkstraSSP {
    private int INF = Integer.MAX_VALUE / 2;
    private int n;//顶点个数
    private String[] node = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N"};//存放顶点
    private int[][] W;//距离矩阵
    private String s;//源点
    private ArrayList<String> S;//最短路径的顶点集合
    private HashMap<String,Integer> d;//源点s到所有顶点的距离
    private ArrayList<String> Q;//基于顶点距离值的最小优先队列
    private HashMap<String,String> prev;//前一个顶点
    public NS_DijkstraSSP(int n,int[][] W,String s){
        this.n = n;
        this.W = W;
        this.s = s;
        S = new ArrayList<>();
        d = new HashMap<>();
        prev = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(node[i].equals(s)){
                d.put(node[i],0);
            }else {
                d.put(node[i],INF);
            }
            prev.put(node[i],s);
        }
        Q = new ArrayList<>();
        Q.add(s);
    }
    public void dijkstra(){
        while (Q.size() != 0){
            String v = getVfromQ();
            S.add(v);
            Q.remove(v);
            traversalU(v);
        }
    }
    public String getVfromQ(){
        //在Q中获取距离值最小的顶点v
        String v = Q.get(0);
        int min = d.get(v);
        for(int i = 0;i < Q.size();i++){
           String ss = Q.get(i);
           int dd = d.get(ss);
           if(dd < min){
               min = dd;
               v = ss;
           }
        }
        return v;
    }
    public void traversalU(String v){
        //对v的各邻居结点u进行遍历
        int i = v.charAt(0) - 'A';
        for(int j = 0;j < n;j++){
            String u = node[j];
            if(!S.contains(u)){
                if(W[i][j] + d.get(v) < d.get(u)){
                    d.put(u,W[i][j] + d.get(v));
                    prev.put(u,v);
                    Q.add(u);
                }
            }
        }
    }
    public void print(){
        for(int i = 0;i < n;i++){
            if(!node[i].equals(s)){
                System.out.print(node[i] + "，" + d.get(node[i])+"：");
                String[] result = new String[n];
                String end = node[i];
                String last = prev.get(end);
                result[n - 1] = end;
                result[n - 2] = last;
                int m = 3;
                while(!last.equals(s)){
                    last = prev.get(last);
                    result[n - m] = last;
                    m++;
                }
                for(int a = 0;a < n;a++){
                    if(result[a] != null){
                        if(a == n-1){
                            System.out.print(result[a]);
                        }else{
                            System.out.print(result[a] + "-");
                        }
                    }
                }
                System.out.println();
            }
        }
    }
    public static void main(String[]args){
        int INF = Integer.MAX_VALUE / 2;
        int n1 = 7;
        int[][] W1 = {
                {0,1,4,INF,INF,INF,INF},
                {1,0,INF,3,6,INF,INF},
                {4,INF,0,2,INF,5,INF},
                {INF,3,2,0,2,4,INF},
                {INF,6,INF,2,0,2,7},
                {INF,INF,5,4,2,0,6},
                {INF,INF,INF,INF,7,6,0}
        };
        String s1 = "A";
        String s2 = "B";
        NS_DijkstraSSP ds = new NS_DijkstraSSP(n1,W1,s2);
        ds.dijkstra();
        ds.print();
    }
}

2.Prim最小生成树

import java.util.ArrayList;
import java.util.HashMap;

/**
 *  @author: cuttle
 *  @Date: 2020/11/4 21:00
 *  @Description: 最小生成树的Prim算法，贪心法
 */
public class NS_PrimMST {
    private int INF = Integer.MAX_VALUE / 2;
    private int n;//顶点个数
    private String[] node = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N"};//存放顶点
    private int[][] W;//距离矩阵
    private String s;//源点
    private ArrayList<String> S;//以s为根的MST的子树集合
    private HashMap<String,Integer> d;//相连边的距离数组
    private ArrayList<String> Q;//S中的顶点与直接相连的S外的集合
    private HashMap<String,String> prev;//前一个顶点
    private int weight;//最小生成树的权重
    public NS_PrimMST(int n,int[][] W,String s){
        this.n = n;
        this.W = W;
        this.s = s;
        S = new ArrayList<>();
        d = new HashMap<>();
        prev = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(node[i].equals(s)){
                d.put(node[i],0);
            }else {
                d.put(node[i],INF);
            }
            prev.put(node[i],s);
        }
        Q = new ArrayList<>();
        Q.add(s);
    }
    public void prim(){
        while (Q.size() != 0){
            String v = getVfromQ();
            S.add(v);
            Q.remove(v);
            traversalU(v);
        }
    }
    public String getVfromQ(){
        //在Q中获取距离值最小的顶点v
        String v = Q.get(0);
        int min = d.get(v);
        for(int i = 0;i < Q.size();i++){
            String ss = Q.get(i);
            int dd = d.get(ss);
            if(dd < min){
                min = dd;
                v = ss;
            }
        }
        return v;
    }
    public void traversalU(String v){
        //对v的各邻居结点u进行遍历
        int i = v.charAt(0) - 'A';
        for(int j = 0;j < n;j++){
            String u = node[j];
            if(!S.contains(u)){
                if(W[i][j]< d.get(u)){
                    d.put(u,W[i][j]);
                    prev.put(u,v);
                    Q.add(u);
                }
            }
        }
    }
    public void print(){
        for(int i = 0;i < n;i++){
            if(!node[i].equals(s)){
                System.out.print(node[i] + "，");
                weight += d.get(node[i]);
                String[] result = new String[n];
                String end = node[i];
                String last = prev.get(end);
                result[n - 1] = end;
                result[n - 2] = last;
                int m = 3;
                while(!last.equals(s)){
                    last = prev.get(last);
                    result[n - m] = last;
                    m++;
                }
                for(int a = 0;a < n;a++){
                    if(result[a] != null){
                        if(a == n-1){
                            System.out.print(result[a]);
                        }else{
                            System.out.print(result[a] + "-");
                        }
                    }
                }
                System.out.println();
            }
        }
        System.out.println(weight);
    }
    public static void main(String[]args){
        int INF = Integer.MAX_VALUE / 2;
        int n1 = 7;
        int[][] W1 = {
                {0,1,4,INF,INF,INF,INF},
                {1,0,2,3,6,4,INF},
                {4,2,0,INF,5,5,INF},
                {INF,3,INF,0,2,INF,INF},
                {INF,6,5,2,0,2,7},
                {INF,4,5,INF,2,0,6},
                {INF,INF,INF,INF,7,6,0}
        };
        String s1 = "A";
        String s2 = "B";
        NS_PrimMST ds = new NS_PrimMST(n1,W1,s2);
        ds.prim();
        ds.print();
    }
}

3.Kruskal算法求最小生成树

import java.util.ArrayList;
import java.util.HashMap;

/**
 *  @author: cuttle
 *  @Date: 2020/11/11 16:32
 *  @Description: 图的最小生成树Kruskal算法
 */
public class NS_KruskalMST {
    private String[] vName = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N"};
    private int vNum;//顶点个数
    private int[][] WMatrix;//权矩阵
    private ArrayList<Edges> edges;//所有的边集合
    private HashMap<Integer,ArrayList<String>> vSet;//点的集合
    private ArrayList<Edges> MST;//最小生成树边的集合
    public NS_KruskalMST(int vNum,int[][] WMatrix,String begin){
        this.vNum = vNum;
        this.WMatrix = WMatrix;
        edges = new ArrayList<>();
        vSet = new HashMap<>();
        MST = new ArrayList<>();
        init();
    }
    public void init(){
        //创建边集合
        for(int i = 0;i < vNum;i++){
            for(int j = i;j < vNum;j++){
                Edges e = new Edges(vName[i],vName[j],WMatrix[i][j]);
                edges.add(e);
            }
        }
        //创建顶点集合
        for(int i = 0;i < vNum;i++){
            ArrayList<String> v = new ArrayList<>();
            v.add(vName[i]);
            vSet.put(i,v);
        }
    }
    public void kruskal(){
        while(MST.size() < vNum - 1){
            //找最小的边
            int min = 0;
            for(int i = 0;i < edges.size();i++){
                if(edges.get(i).getWeight() < edges.get(min).getWeight()){
                    min = i;
                }
            }
            Edges minEdge = edges.get(min);
            edges.remove(min);
            String u = minEdge.getU();
            String v = minEdge.getV();
            if(!isSameSet(u,v)){
                unionSets(u,v);
                MST.add(minEdge);
            }
        }
    }
    public boolean isSameSet(String u,String v){
        int uN = -1;
        int vN = -1;//记录两个顶点在hashMap中的位置
        for(int i = 0;i < vSet.size();i++){
            if(vSet.get(i)!=null && vSet.get(i).contains(u)){
                uN = i;
            }
            if(vSet.get(i)!=null && vSet.get(i).contains(v)){
                vN = i;
            }
        }
        return uN == vN;
    }
    public void unionSets(String u,String v){
        int uN = -1;
        int vN = -1;//记录两个顶点在hashMap中的位置
        for(int i = 0;i < vSet.size();i++){
            ArrayList<String> temp = vSet.get(i);
            if(vSet.get(i)!=null && temp.contains(u)){
                uN = i;
            }
            if(vSet.get(i)!=null && temp.contains(v)){
                vN = i;
            }
        }
        for(int m = vSet.get(vN).size() - 1;m >= 0;m--){
            vSet.get(uN).add(vSet.get(vN).get(m));//合并v和u所在集合集合
            vSet.get(vN).remove(m);
        }
    }
    public void printMST(){
        for (Edges ee:MST
             ) {
            System.out.println(ee.toString());
        }
    }
    public static void main(String[]args){
        int INF = Integer.MAX_VALUE / 2;
        int vNum = 7;
        String begin = "A";
        int[][] WMatrix = {
                {0,1,4,INF,INF,INF,INF},
                {1,0,INF,3,6,INF,INF},
                {4,INF,0,2,INF,5,INF},
                {INF,3,2,0,2,4,INF},
                {INF,6,INF,2,0,2,7},
                {INF,INF,5,4,2,0,6},
                {INF,INF,INF,INF,7,6,0}
        };
        NS_KruskalMST k = new NS_KruskalMST(vNum,WMatrix,begin);
        k.kruskal();
        k.printMST();
    }
}
class Edges{
    private String u;
    private String v;//<u,v>
    private int weight;//权重
    public Edges(String u,String v,int weight){
        this.u = u;
        this.v = v;
        this.weight = weight;
    }
    public String getU(){
        return u;
    }
    public String getV(){
        return v;
    }
    public int getWeight(){ return weight; }

    @Override
    public String toString() {
        return "Edges{" +
                "u='" + u + '\'' +
                ", v='" + v + '\'' +
                ", weight=" + weight +
                '}';
    }
}

本文地址：https://blog.csdn.net/weixin_44777287/article/details/109562288