human
Write me a code to minimum cost to connect all cities and the other steps required given the following:
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"
How can the above be solved in Python?
assistant
#Here is code to minimum cost to connect all cities and the other steps required.
 def minnode ( n , keyval , mstset ) :
	mini = 999999999999
	mini_index = None
	for i in range ( n ) :
		if ( mstset [ i ] == False and keyval [ i ] < mini ) :
			mini = keyval [ i ]
			mini_index = i
	return mini_index
def findcost ( n , city ) :
	parent = [ None ] * n
	keyval = [ None ] * n
	mstset = [ None ] * n
	for i in range ( n ) :
		keyval [ i ] = 9999999999999
		mstset [ i ] = False
	parent [ 0 ] = - 1
	keyval [ 0 ] = 0
	for i in range ( n - 1 ) :
		u = minnode ( n , keyval , mstset )
		mstset [ u ] = True
		for v in range ( n ) :
			if ( city [ u ] [ v ] and mstset [ v ] == False and city [ u ] [ v ] < keyval [ v ] ) :
				keyval [ v ] = city [ u ] [ v ]
				parent [ v ] = u
	cost = 0
	for i in range ( 1 , n ) :
		cost += city [ parent [ i ] ] [ i ]
	print ( cost )
if __name__ == ' _ _ main _ _ ' :
	n1 = 5
	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 ] ]
	findcost ( n1 , city1 )
	n2 = 6
	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 ] ]
	findcost ( n2 , city2 )