The assignment is to implement an algorithm to determine if the minimum weight spanning tree of an edge-weighted graph, connected graph , with no self-loops or parallel edges, is the same when using Prims algorithm as it is when using Kruskals algorithm. The edge weights in G will be real numbers greater than 0 and will not necessarily be distinct. A Java template has been provided containing an empty method PrimVsKruskal, which takes a single argument consisting of a weighted adjacency matrix for an edge-weighted graph with real number edge weights all greater than 0. The expected behavior of the method is as follows:

Input: An array , of type double, representing an edge-weighted graph. Output: A boolean value which is true if the Prims MST equals the Kruskals MST and false otherwise.

A correct implementation of the PrimVsKruskal class will find the minimum weight spanning tree using the textbooks implementation of Prims algorithm (eager version) and the minimum weight spanning tree using the textbooks implementation of Kruskals algorithm and compare. If they are the same it returns true, otherwise false. You must use the provided Java template as the basis of your submission, and put your implementation inside the PrimVsKruskal method in the template. You may not change the name, return type or parameters of the PrimVsKruskal method. You may add additional methods as needed. You may use any of the classes provided by the textbook as your code will be run with the algs4.jar file. Most likely you will use some or all of the following: UF class, IndexMinPQ class, MinPQ class, Edge class, Queue class, etc. The main method in the template contains code to help you test your implementation by reading an adjacency matrix from a file. You may modify the main method to help with testing, but only the contents of the PrimVsKruskal method

The most difficult but most efficient way to solve it also involves working directly with the adjacency matrix but here you build the two trees concurrently, testing the consistency of the trees after adding each edge. We will call this an early detection system, which will recognize if two trees are unequal before completion of the trees.

input format:

10 0 5 0 0 0 0 0 0 0 0 5 0 4 0 0 1 3 9 0 0 0 4 0 0 0 0 6 4 0 0 0 0 0 0 0 0 4 0 0 4 0 0 0 0 0 0 8 0 2 9 0 1 0 0 0 0 0 0 0 0 0 3 6 4 8 0 0 0 1 0 0 9 4 0 0 0 0 0 0 8 0 0 0 0 2 0 1 0 0 0 0 0 0 4 9 0 0 8 0 0

code template:

*/ import edu.princeton.cs.algs4.*; import java.util.Scanner; import java.io.File; //Do not change the name of the PrimVsKruskal class public class PrimVsKruskal{ /* PrimVsKruskal(G) Given an adjacency matrix for connected graph G, with no self-loops or parallel edges, determine if the minimum spanning tree of G found by Prim's algorithm is equal to the minimum spanning tree of G found by Kruskal's algorithm. If G[i][j] == 0.0, there is no edge between vertex i and vertex j If G[i][j] > 0.0, there is an edge between vertices i and j, and the value of G[i][j] gives the weight of the edge. No entries of G will be negative. */ static boolean PrimVsKruskal(double[][] G){ int n = G.length; /* Build the MST by Prim's and the MST by Kruskal's */ /* (You may add extra methods if necessary) */ /* ... Your code here ... */ /* Determine if the MST by Prim equals the MST by Kruskal */ boolean pvk = true; /* ... Your code here ... */ return pvk; } /* main() Contains code to test the PrimVsKruskal function. You may modify the testing code if needed, but nothing in this function will be considered during marking, and the testing process used for marking will not execute any of the code below. */ public static void main(String[] args) { Scanner s; if (args.length > 0){ try{ s = new Scanner(new File(args[0])); } catch(java.io.FileNotFoundException e){ System.out.printf("Unable to open %s ",args[0]); return; } System.out.printf("Reading input values from %s. ",args[0]); }else{ s = new Scanner(System.in); System.out.printf("Reading input values from stdin. "); } int n = s.nextInt(); double[][] G = new double[n][n]; int valuesRead = 0; for (int i = 0; i < n && s.hasNextDouble(); i++){ for (int j = 0; j < n && s.hasNextDouble(); j++){ G[i][j] = s.nextDouble(); if (i == j && G[i][j] != 0.0) { System.out.printf("Adjacency matrix contains self-loops. "); return; } if (G[i][j] < 0.0) { System.out.printf("Adjacency matrix contains negative values. "); return; } if (j < i && G[i][j] != G[j][i]) { System.out.printf("Adjacency matrix is not symmetric. "); return; } valuesRead++; } } if (valuesRead < n*n){ System.out.printf("Adjacency matrix for the graph contains too few values. "); return; } boolean pvk = PrimVsKruskal(G); System.out.printf("Does Prim MST = Kruskal MST? %b ", pvk); } }