This Java code implements Prim's Algorithm to find the Minimum Spanning Tree (MST) of a given weighted graph represented by a cost matrix. It reads the cost matrix and number of vertices from user input, then calculates and displays the minimum cost edges that form the MST along with the total minimum cost.
The algorithm uses a greedy approach, beginning from an initial vertex and progressively adding the shortest edge that connects a new vertex to the growing MST. The pr function performs the core operations, updating the minimum cost and the list of nearest vertices.
Test Case:
Input:
Number of vertices: 4
Cost matrix:
0 2 0 6
2 0 3 8
0 3 0 0
6 8 0 0
Output
Enter the number of vertices:
4
Enter the cost matrix:
Min Tree edges are
1: Minimum edge is <1, 2> Cost: 2
2: Minimum edge is <2, 3> Cost: 3
3: Minimum edge is <1, 4> Cost: 6
Minimum cost: 11
siriak
commented
1 month ago
This Java code implements Prim's Algorithm to find the Minimum Spanning Tree (MST) of a given weighted graph represented by a cost matrix. It reads the cost matrix and number of vertices from user input, then calculates and displays the minimum cost edges that form the MST along with the total minimum cost.
The algorithm uses a greedy approach, beginning from an initial vertex and progressively adding the shortest edge that connects a new vertex to the growing MST. The pr function performs the core operations, updating the minimum cost and the list of nearest vertices.
Test Case: Input: Number of vertices: 4 Cost matrix: 0 2 0 6 2 0 3 8 0 3 0 0 6 8 0 0 Output Enter the number of vertices: 4 Enter the cost matrix: Min Tree edges are 1: Minimum edge is <1, 2> Cost: 2 2: Minimum edge is <2, 3> Cost: 3 3: Minimum edge is <1, 4> Cost: 6 Minimum cost: 11
clang-format -i --style=file path/to/your/file.java