Prim 's Algorithm (Simple Implementation for Adjacency Matrix Representation) | A simple Java implementation to find minimum spanning tree for adjacency representation . ; Returns true if edge u - v is a valid edge to be include in MST . An edge is valid if one end is already included in MST and other is not in MST . ; Include first vertex in MST ; Keep adding edges while number of included edges does not become V - 1. ; Find minimum weight valid edge . ; Driver Code ; Let us create the following graph 2 3 ( 0 ) -- ( 1 ) -- ( 2 ) | / \ | 6 | 8 / \ 5 | 7 | / \ | ( 3 ) -- -- -- - ( 4 ) 9 ; Print the solution
import java . util . * ; class GFG { static int V = 5 ; static int INT_MAX = Integer . MAX_VALUE ; static boolean isValidEdge ( int u , int v , boolean [ ] inMST ) { if ( u == v ) return false ; if ( inMST [ u ] == false && inMST [ v ] == false ) return false ; else if ( inMST [ u ] == true && inMST [ v ] == true ) return false ; return true ; } static void primMST ( int cost [ ] [ ] ) { boolean [ ] inMST = new boolean [ V ] ; inMST [ 0 ] = true ; int edge_count = 0 , mincost = 0 ; while ( edge_count < V - 1 ) { int min = INT_MAX , a = - 1 , b = - 1 ; for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { if ( cost [ i ] [ j ] < min ) { if ( isValidEdge ( i , j , inMST ) ) { min = cost [ i ] [ j ] ; a = i ; b = j ; } } } } if ( a != - 1 && b != - 1 ) { System . out . printf ( "Edge %d:(%d, %d) cost: %d NEW_LINE", edge_count++, a, b, min); mincost = mincost + min ; inMST [ b ] = inMST [ a ] = true ; } } System . out . printf ( " Minimum cost = % d ", mincost); } public static void main ( String [ ] args ) { int cost [ ] [ ] = { { INT_MAX , 2 , INT_MAX , 6 , INT_MAX } , { 2 , INT_MAX , 3 , 8 , 5 } , { INT_MAX , 3 , INT_MAX , INT_MAX , 7 } , { 6 , 8 , INT_MAX , INT_MAX , 9 } , { INT_MAX , 5 , 7 , 9 , INT_MAX } } ; primMST ( cost ) ; } }