找到一條能夠把所有點連接起來的最短路徑

prim算法

用一個數(shù)組minDist來記錄每一個節(jié)點距離最小生成樹的最近距離，

用一個boolean數(shù)組visited記錄節(jié)點是否加入最小生成樹

算法流程：

1. 選擇離最小生成樹最近的（minDist值最斜栌洹），還沒有加入最小生成樹（visited為false）的節(jié)點

2. 標記節(jié)點加入最小生成樹（visited為true）

3. 更新minDist中還沒有加入最小生成樹的節(jié)點的值

   用什么更新？ --因為剛剛加入新的節(jié)點饺藤，用新節(jié)點到這些節(jié)點的距離更新

   (minDist[不是生成樹的節(jié)點] = Math.min(graph[剛加入的節(jié)點][不是生成樹的節(jié)點], minDist[不是生成樹的節(jié)點]))

import java.util.*;

public class Main{
    public static int V;
    public static int E;
    public static int[][] graph;
    public static boolean[] visited;
    //minDist數(shù)組 用來記錄 每一個節(jié)點距離最小生成樹的最近距離
    public static int[] minDist;

    public static void main (String[] args) {
        /* code */
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();

        graph = new int[V+1][V+1];
        visited = new boolean[V+1];
        minDist = new int[V+1];
        Arrays.fill(minDist, 10001);

        //因為val>=0,所以要做一個二維數(shù)組的初始化
        for(int i=1; i<=V; i++){
            Arrays.fill(graph[i], -1);
        }

        for(int i=0; i<E; i++){
            int start = in.nextInt();
            int end = in.nextInt();
            int val = in.nextInt();
            graph[start][end] = val;
            //注意是無向圖
            graph[end][start] = val;
        }

        prim();
        
        int result = 0;
        for(int i=2; i<=V; i++){
            result+=minDist[i];
        }
        System.out.println(result);
    }
    public static void prim(){
        // i循環(huán)的是次數(shù)包斑，一共要做V次（把v個節(jié)點加入生成樹）
        for(int i=0; i<V; i++){
            int min_val = Integer.MAX_VALUE;
            int cur = -1;
            //選擇距離最小生成樹最近的點加入最小生成樹
            for(int j=1; j<=V; j++){
                if(!visited[j]&&minDist[j]<min_val){
                    min_val = minDist[j];
                    cur = j;
                }
            }
            //加入
            visited[cur]=true;
            //更新沒加入最小生成樹的節(jié)點到達最小生成樹的距離
            for(int j=1; j<=V; j++){
                if(!visited[j]&&graph[cur][j]>=0)
                    minDist[j] = Math.min(graph[cur][j], minDist[j]);
            }
        }
    }
}

Kruskal

用到并查集的知識

1. 用LinkedList記錄所有的邊，并按照權(quán)值排序

2. 遍歷有序（升序）的邊：

   • 如果邊的兩個點不在同一個集合涕俗，則加入最小生成樹（用result記錄樹的長度罗丰，所以result要+邊長，且要把兩個點并為同一個集合）
   • 如果在同一個集合再姑，直接跳過這個邊萌抵，看下一條邊

import java.util.*;

public class Main{
    public static int V;
    public static int E;
    public static LinkedList<int[]> edges;
    public static int[] father;
    public static int result;

    public static void main (String[] args) {
        /* code */
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();

        edges = new LinkedList<>();
        father = new int[V+1];
        result = 0;
        for(int i=1; i<=V; i++){
            father[i] = i;
        }
        for(int i=0; i<E; i++){
            int start = in.nextInt();
            int end = in.nextInt();
            int val = in.nextInt();
            edges.add(new int[]{start, end, val});
        }
        //List自定義排序規(guī)則！Ｔ啤绍填！
        edges.sort(Comparator.comparingInt(o -> o[2]));
        kruskal();
        System.out.println(result);
    }
    public static int find(int u){
        if(u==father[u]) return u;
        else return father[u] = find(father[u]);
    }
    public static boolean isSame(int u, int v){
        u = find(u);
        v = find(v);
        return u==v;
    }

    public static void join(int u, int v) {
        u = find(u);
        v = find(v);
        father[v] = u;
    }

    public static void kruskal(){
        //V個節(jié)點，加V-1條邊就行了栖疑，所以需要重復(fù)V-1次
        for(int i=1; i<V; i++){
            int[] edge = edges.removeFirst();
            while(isSame(edge[0], edge[1])){
                edge = edges.removeFirst();
            }
            result += edge[2];
            join(edge[0], edge[1]);
        }
    }
}