普里姆算法

package com.zhang.reflection.面试.算法模版.图.最小生成树;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class 普里姆算法 {
    static class Node {
        public int from;
        public int to;
        public int weight;
        public Node(int from,int to,int weight){
            this.from=from;
            this.to=to;
            this.weight=weight;
        }
    }
    static ArrayList<Node>[] graph;
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st=new StreamTokenizer(br);
        st.nextToken();n=(int)st.nval;
        st.nextToken();m=(int)st.nval;
        graph=new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            st.nextToken();int from=(int)st.nval;
            st.nextToken();int to=(int)st.nval;
            st.nextToken();int weight=(int)st.nval;
            Node node1=new Node(from,to,weight);
            Node node2=new Node(to,from,weight);
            graph[from].add(node1);
            graph[to].add(node2);
        }
        prim(1);
    }
    private static void prim(int start) {
        PriorityQueue<Node> heap=new PriorityQueue<>((a, b)->a.weight-b.weight);
        int sum=0;
        int num=0;
        boolean[] visited=new boolean[n+1];
        visited[start]=true;
        for(Node node:graph[start]){
            heap.offer(node);
        }
        while(!heap.isEmpty()){
            Node cur=heap.poll();
            if(!visited[cur.to]){
                num++;
                sum+=cur.weight;
                visited[cur.to]=true;
                for(Node node:graph[cur.to]){
                    if(!visited[node.to]){
                        heap.offer(node);
                    }
                }
            }
        }
        if(num!=n-1){
            System.out.println("orz");
        }else{
            System.out.println(sum);
        }
    }
}