Problem 107

p107.py

def PrimsAlgorithm(graph):
    #Find dimension of graph, as well as previous weight
    dimension = len(graph)
    Previous_Weight = sum([graph[x][y] for x in range(dimension) for y in range(x+1, dimension) if graph[x][y] != 0])
    
    Tree = set([0]) #Step 1
    New_Weight = 0
    
    for x in range(dimension - 1):
        Minimum_edge, Corresponding_vertex = min([(graph[x][y], y) for x in Tree \
                                                  for y in range(dimension) if y not in Tree and graph[x][y] != 0])
        #Step 2
        #We find the minimum edge and he corresponding vertex it is linking too, we search through the nodes that
        #we have already been through, and take the minimum of all the ones they connect to, make sure that
        #We do not reconnect with an already visited node or traverse a non-existing edge
        
        #Add the new node and edge to the sum
        Tree.add(Corresponding_vertex)
        New_Weight += Minimum_edge
        
        
        if len(Tree) == dimension: #Step 3, if we have every vertex we stop
            break
    
    return Previous_Weight - New_Weight