Java Programming: Right now Im trying to find a proper way to store the input of

Question

Java Programming:

Right now Im trying to find a proper way to store the input of the Scanner.in file this problem deals with minimum spanning trees. The input file looks like this:

3

2 1

1 2 5

3 1

1 2 2

4 4

1 2 2

2 3 3

3 4 1

1 4 4

Okay, so the first line with 1 number indicates the number of cases. The lines with 2 numbers on it indicate the number of nodes and the number of edges. The lines with 3 digits indicates the starting node, the ending node and the weight of the edge. Im just trying to figure out how to store and these values in a good data-type to start out with. Also Im using Scanner input = new Scanner(System.in); to read in these values from a input.in file. Any good approaches to take in this data and sort it porpoerly for a MST?

Explanation / Answer

There are two ways to find the MST, using PRIM'S ALGORITHMS and KRUSHKAL'S ALGORITHM.

In case you want to implement the mst using prim's algo, then input the edges in some matrix and use it.

The easiest approach is to use class and hash to implement krushkal's algorithm.

class Node{

int start_vertex;

int end_vertex;

int weight;

}

Make seperate Node class objects for each set of input value (vertex1, vertex2, edge weight) and add these nodes into some arraylist. Now, using a comparator class object, sort the nodes in the arraylist based on the weights of the edges.

Create a hashset to store the visited vertices. Now, traverse each node in the arraylist. If both the starting vertex and the ending vertex have already been visited(present in the hashset), ignore this object and more to the next one. If any of the starting or ending vertex of the object have not been visited yet, add that vertex to the hashset and include this edge startingvertex->endingvertex into the final result. at the end, you will have the set of all the edges present in the MST.

Hope you understood the logic to find the MST.

In case you want the complete program, let me know , i'll get it done for you. :)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.