Day57 图论part07

今天在学习prim 和 kruskal的同时，也要清楚这两个算法的区别所在。

prim算法精讲

代码随想录

import java.util.*;

public class Main{
    public static void main (String[] args) {
        //prime算法
        //1.选择距离最小生成树最近的非树节点
        //2.将该节点加入到生成树里面
        //3.更新其他非树节点到最小生成树的距离
        
        Scanner scanner = new Scanner(System.in);
        int v = scanner.nextInt();
        int e = scanner.nextInt();
        int[][] graph = new int[v+1][v+1];
        for(int[] edges : graph){
            Arrays.fill(edges, 10001);
        }
        
        for(int i = 0; i < e; i++){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int len = scanner.nextInt();
            graph[n][m] = len;
            graph[m][n] = len;//无向图，两个方向都要构建；
        }
        
        int[] minDist = new int[v+1];
        Arrays.fill(minDist, 10001);
        
        boolean[] isInTree = new boolean[v+1];
        int[] farther = new int[v+1];
        
        for(int j = 1; j <= v; j++){
            int cur = -1;
            int mindist = Integer.MAX_VALUE;
            
            for(int i = 1; i <= v; i++){