Kruskal_Algorithm.java / Prim_Algorithm.java

Kruskal_Algorithm.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Kruskal_Algorithm {

    static int V, E, parents[];
    static Edge[] edgeList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 3
        E = Integer.parseInt(st.nextToken()); // 3

        edgeList = new Edge[E];
        parents = new int[V + 1];

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            edgeList[i] = new Edge(a, b, c);
        }
        System.out.println(kruskal());
    }

    private static int kruskal(){
        int res=0;
        int cnt=0;

        Arrays.sort(edgeList);
        make();

        for(Edge edge : edgeList){
            if(union(edge.from, edge.to)){
                res += edge.weight;

                if(++cnt == V-1) return res;
            }
        }
        return res;
    }

    private static boolean union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);

        if(aRoot == bRoot) return false;
        parents[aRoot] = bRoot;
        return true;
    }

    private static int find(int a) {
        if(a == parents[a]) return a;
    return parents[a] = find(parents[a]);
    }

    private static void make() {
        for(int i=0; i<=V; i++){
            parents[i] =i;
        }
    }


    static class Edge implements Comparable<Edge> {
        int from, to, weight;


        public Edge(int from, int to, int weight) {
            super();
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o){
            return Integer.compare(this.weight, o.weight);
        }

    }
}

Prim_Algorithm.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Prim_Algorithm {
    static int V, E;
    static ArrayList<Node>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 3
        E = Integer.parseInt(st.nextToken()); // 3

        adj = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            adj[a].add(new Node(b, c));
            adj[b].add(new Node(a, c));

        }
        System.out.println(prim());
    }

    private static Long prim(){
        boolean[] visited = new boolean[V + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1,0));

        long res = 0;
        int cnt =0;

        while(!pq.isEmpty()){
            Node edge = pq.poll();
            if(visited[edge.to]) continue;

            res +=edge.weight;
            visited[edge.to] = true;

            if(++cnt == V) return res;

            for (int i = 0; i < adj[edge.to].size(); i++) {
                Node next = adj[edge.to].get(i);
                if(visited[next.to]) continue;

                pq.add(next);
            }
        }

        return res;
    }

    static class Node implements Comparable<Node> {
        int to, weight;

        public Node(int to, int weight) {
            super();
            this.to = to;
            this.weight = weight;
        }
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    
}