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
kruskals_quick_union.py 文件源码
python
阅读 27
收藏 0
点赞 0
评论 0
评论列表
文章目录