kruskals_quick_union.py 文件源码

def kruskals(G, pos):
    eLen = len(G.edges()) # eLen denotes the number of edges in G
    vLen = len(G.nodes()) # vLen denotes the number of vertices in G
    mst = [] # mst contains the MST edges
    mstFlag = {} # mstFlag[i] will hold true if the edge i has been processed for MST
    for i in [ (u, v, edata['length']) for u, v, edata in G.edges(data = True) if 'length' in edata ]:
        mstFlag[i] = False 

    parent = [None] * vLen # parent[i] will hold the vertex connected to i, in the MST
    order = [None] * vLen   # order[i] will hold the order of appearance of the node in the MST
    for v in range(vLen):
        parent[v] = v
        order[v] = 0
    while len(mst) < vLen - 1 :
        curr_edge = getMin(G, mstFlag) # pick the smallest egde from the set of edges
        mstFlag[curr_edge] = True # update the flag for the current edge
        y = findRoot(parent, curr_edge[1])
        x = findRoot(parent, curr_edge[0])
        # adds the edge to MST, if including it doesn't form a cycle
        if x != y:
            mst.append(curr_edge)
            union(parent, order, x, y)
        # Else discard the edge
    # marks the MST edges with red
    for X in mst:
        if (X[0], X[1]) in G.edges():
            nx.draw_networkx_edges(G, pos, edgelist = [(X[0], X[1])], width = 2.5, alpha = 0.6, edge_color = 'r')
    return



# takes input from the file and creates a weighted graph