prims.py 文件源码

def prims(G, pos):
    V = len(G.nodes()) # V denotes the number of vertices in G
    dist = [] # dist[i] will hold the minimum weight edge value of node i to be included in MST
    parent = [None]*V # parent[i] will hold the vertex connected to i, in the MST edge
    mstSet = [] # mstSet[i] will hold true if vertex i is included in the MST
    #initially, for every node, dist[] is set to maximum value and mstSet[] is set to False
    for i in range(V):
        dist.append(sys.maxsize)
        mstSet.append(False)
    dist[0] = 0
    parent[0]= -1 #starting vertex is itself the root, and hence has no parent
    for count in range(V-1):
        u = minDistance(dist, mstSet, V) #pick the minimum distance vertex from the set of vertices
        mstSet[u] = True
        #update the vertices adjacent to the picked vertex
        for v in range(V):
            if (u, v) in G.edges():
                if mstSet[v] == False and G[u][v]['length'] < dist[v]:
                    dist[v] = G[u][v]['length']
                    parent[v] = u
    for X in range(V):
        if parent[X] != -1: #ignore the parent of the starting node
            if (parent[X], X) in G.edges():
                nx.draw_networkx_edges(G, pos, edgelist = [(parent[X], X)], width = 2.5, alpha = 0.6, edge_color = 'r')
    return



#takes input from the file and creates a weighted graph