Minimum cost to connect all cities | Function to find out minimum valued node among the nodes which are not yet included in MST ; Loop through all the values of the nodes which are not yet included in MST and find the minimum valued one . ; Function to find out the MST and the cost of the MST . ; Array to store the parent node of a particular node . ; Array to store key value of each node . ; Boolean Array to hold bool values whether a node is included in MST or not . ; Set all the key values to infinite and none of the nodes is included in MST . ; Start to find the MST from node 0. Parent of node 0 is none so set - 1. key value or minimum cost to reach 0 th node from 0 th node is 0. ; Find the rest n - 1 nodes of MST . ; First find out the minimum node among the nodes which are not yet included in MST . ; Now the uth node is included in MST . ; Update the values of neighbor nodes of u which are not yet included in MST . ; Find out the cost by adding the edge values of MST . ; Driver Code ; Input 1 ; Input 2
def minnode ( n , keyval , mstset ) : NEW_LINE INDENT mini = 999999999999 NEW_LINE mini_index = None NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( mstset [ i ] == False and keyval [ i ] < mini ) : NEW_LINE INDENT mini = keyval [ i ] NEW_LINE mini_index = i NEW_LINE DEDENT DEDENT return mini_index NEW_LINE DEDENT def findcost ( n , city ) : NEW_LINE INDENT parent = [ None ] * n NEW_LINE keyval = [ None ] * n NEW_LINE mstset = [ None ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT keyval [ i ] = 9999999999999 NEW_LINE mstset [ i ] = False NEW_LINE DEDENT parent [ 0 ] = - 1 NEW_LINE keyval [ 0 ] = 0 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT u = minnode ( n , keyval , mstset ) NEW_LINE mstset [ u ] = True NEW_LINE for v in range ( n ) : NEW_LINE INDENT if ( city [ u ] [ v ] and mstset [ v ] == False and city [ u ] [ v ] < keyval [ v ] ) : NEW_LINE INDENT keyval [ v ] = city [ u ] [ v ] NEW_LINE parent [ v ] = u NEW_LINE DEDENT DEDENT DEDENT cost = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT cost += city [ parent [ i ] ] [ i ] NEW_LINE DEDENT print ( cost ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n1 = 5 NEW_LINE city1 = [ [ 0 , 1 , 2 , 3 , 4 ] , [ 1 , 0 , 5 , 0 , 7 ] , [ 2 , 5 , 0 , 6 , 0 ] , [ 3 , 0 , 6 , 0 , 0 ] , [ 4 , 7 , 0 , 0 , 0 ] ] NEW_LINE findcost ( n1 , city1 ) NEW_LINE n2 = 6 NEW_LINE city2 = [ [ 0 , 1 , 1 , 100 , 0 , 0 ] , [ 1 , 0 , 1 , 0 , 0 , 0 ] , [ 1 , 1 , 0 , 0 , 0 , 0 ] , [ 100 , 0 , 0 , 0 , 2 , 2 ] , [ 0 , 0 , 0 , 2 , 0 , 2 ] , [ 0 , 0 , 0 , 2 , 2 , 0 ] ] NEW_LINE findcost ( n2 , city2 ) NEW_LINE DEDENT