We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
defprims(n,edges,start):dedges={}foredgeinedges:try:dedges[edge[0]].append((edge[0],edge[1],edge[2]))exceptKeyError:dedges[edge[0]]=[(edge[0],edge[1],edge[2])]try:dedges[edge[1]].append((edge[1],edge[0],edge[2]))exceptKeyError:dedges[edge[1]]=[(edge[1],edge[0],edge[2])]# using a dict to keep track of which nodes still need to be included# will delete keys from dict as nodes get added to spanning treenodes_remaining={node:Nonefornodeinrange(1,n+1)}tnodes,tedges=[start],[]delnodes_remaining[start]whilenodes_remaining:curr_min=float('inf')fortnodeintnodes:foredgeindedges[tnode]:try:nodes_remaining[edge[1]]ifedge[2]<curr_min:curr_min,curr_min_edge=edge[2],edgeexceptKeyError:passtnodes.append(curr_min_edge[1])delnodes_remaining[curr_min_edge[1]]tedges.append(curr_min_edge)weights=[edge[2]foredgeintedges]returnsum(weights)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prim's (MST) : Special Subtree
You are viewing a single comment's thread. Return to all comments →
Python 3