I am confused why we need two for loops for the solution. What can possibly go wrong if we use one loop for it?
My Solution
def find_min_spanning_tree(self):
# Initializing minimum weight for result
weight = 0
# Taking first vertex as starting point (All vertices need to be covered. So no specific order)
vertex = self.g[0]
# Marking the vertex as visited
vertex.visited = True
# Keeping a count of vertices left to visit
left_to_visit = len(self.g) - 1
# Looping till we have some vertices left to visit (> 0)
while left_to_visit:
# Used for storing the smallest outgoing edge from current vertex
# (To compare with other outgoing vertices from current vertex)
smallest = None
# Looping over all the edges to find out the first non visited edge (Both edge and its destination)
for edge in self.e:
# If non visited edge (Both edge and its destination)
if edge.visited == False and edge.dest.visited == False:
# Updating smallest, if we haven't initialized it. Will be used for comparison
if not smallest:
smallest = edge
# Updating the weight by joining the visited edge (source is visited)
# and joining it to the destination vertex will result in minimum weight
# seen till now
if edge.src.visited == True and smallest and smallest.weight > edge.weight:
smallest = edge
# Adding current weight to total weight to resturn
weight += smallest.weight
# Marking the edge to be visited (so as not to revisit later)
smallest.visited = True
# Marking its destination as visited (The edge is considered in min weight
# which implies it source and destination vertex have been considered)
smallest.dest.visited = True
# Updating the number of vertices which are left to visit now
left_to_visit -= 1
# Returning the minimum weight possible for the graph
return weight