Prim 's Algorithm (Simple Implementation for Adjacency Matrix Representation) | Python3 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
from sys import maxsize NEW_LINE INT_MAX = maxsize NEW_LINE V = 5 NEW_LINE def isValidEdge ( u , v , inMST ) : NEW_LINE INDENT if u == v : NEW_LINE INDENT return False NEW_LINE DEDENT if inMST [ u ] == False and inMST [ v ] == False : NEW_LINE INDENT return False NEW_LINE DEDENT elif inMST [ u ] == True and inMST [ v ] == True : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def primMST ( cost ) : NEW_LINE INDENT inMST = [ False ] * V NEW_LINE inMST [ 0 ] = True NEW_LINE edge_count = 0 NEW_LINE mincost = 0 NEW_LINE while edge_count < V - 1 : NEW_LINE INDENT minn = INT_MAX NEW_LINE a = - 1 NEW_LINE b = - 1 NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT if cost [ i ] [ j ] < minn : NEW_LINE INDENT if isValidEdge ( i , j , inMST ) : NEW_LINE INDENT minn = cost [ i ] [ j ] NEW_LINE a = i NEW_LINE b = j NEW_LINE DEDENT DEDENT DEDENT DEDENT if a != - 1 and b != - 1 : NEW_LINE INDENT print ( " Edge ▁ % d : ▁ ( % d , ▁ % d ) ▁ cost : ▁ % d " % ( edge_count , a , b , minn ) ) NEW_LINE edge_count += 1 NEW_LINE mincost += minn NEW_LINE inMST [ b ] = inMST [ a ] = True NEW_LINE DEDENT DEDENT print ( " Minimum ▁ cost ▁ = ▁ % d " % mincost ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT 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 ] ] NEW_LINE primMST ( cost ) NEW_LINE DEDENT