Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Connect Stars by _Chico_
from math import hypot
def prims_alogirthm(adjDistance) -> int:
"""Given a 2D list of distances in a network, find the minimum spanning tree."""
N,connected_nodes,total_mst_weight,connected_edges = len(adjDistance),[],0,[]
while len(connected_nodes) < N:
if len(connected_nodes) == 0: vertex_to_add = 0
else:
eligible_arcs = [(R,C) for R in range(N) for C in range(N) if C in connected_nodes]
u,v = min(eligible_arcs, key=lambda x:adjDistance[x[0]][x[1]])
vertex_to_add = u; total_mst_weight += adjDistance[u][v]; connected_edges.append((u,v))
connected_nodes.append(vertex_to_add)
for C in range(N): adjDistance[vertex_to_add][C] = float("inf")
return connected_edges
def connect_stars(coords):
distance=lambda a,b:hypot(a[0]-b[0],a[1]-b[1])
adjDistance = [[distance(u,v) for u in coords] for v in coords]
return prims_alogirthm(adjDistance)
June 6, 2021
