Description :
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 Cases:
Test Case 1:
Input:
Number of vertices: 3
Cost matrix:
0 5 1
5 0 4
1 4 0
Expected Output:
Enter the number of vertices:
3
Enter the cost matrix:
Min Tree edges are
1: Minimum edge is <1, 3> Cost: 1
2: Minimum edge is <3, 2> Cost: 4
Minimum cost: 5
Explanation:
In this case, the algorithm selects the edge between vertices 1 and 3 (cost 1) first, then the edge between vertices 3 and 2 (cost 4). The minimum spanning tree cost is 5.
Test Case 2:
Input:
Number of vertices: 5
Cost matrix:
0 2 0 6 0
2 0 3 8 5
0 3 0 7 9
6 8 7 0 0
0 5 9 0 0
Expected Output:
Enter the number of vertices:
5
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
4: Minimum edge is <2, 5> Cost: 5
Minimum cost: 16
What would you like to share?
Description : 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 Cases: Test Case 1: Input: Number of vertices: 3 Cost matrix:
0 5 1 5 0 4 1 4 0 Expected Output: Enter the number of vertices: 3 Enter the cost matrix: Min Tree edges are 1: Minimum edge is <1, 3> Cost: 1 2: Minimum edge is <3, 2> Cost: 4 Minimum cost: 5 Explanation: In this case, the algorithm selects the edge between vertices 1 and 3 (cost 1) first, then the edge between vertices 3 and 2 (cost 4). The minimum spanning tree cost is 5.
Test Case 2: Input: Number of vertices: 5 Cost matrix: 0 2 0 6 0 2 0 3 8 5 0 3 0 7 9 6 8 7 0 0 0 5 9 0 0 Expected Output: Enter the number of vertices: 5 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 4: Minimum edge is <2, 5> Cost: 5 Minimum cost: 16
Prims Algorithm Using Greedy Techniue for Minimum Spanning Tree.docx
Additional information
No response