Minimum Spanning Trees

Kruskal.py

MST-Kruskal(G, w)    		
  A = ∅
  for each vertex v ∈ G.V
    Make-Set(v)
  sort the edges of E by increasing w (weight) value
  for each edge (u, v) ∈ E (taken in weight order)
    if Find-Set(u) ≠ Find-Set(v)
     A = A ∪ {(u, v)}
     Union(u, v)
  return A

Prim.py

MST-Prim(G, w, r)        # r is an arbitrarily chosen vertex
  for each u ∈ G.V
    u.key = ∞
    u.π = NIL
  r.key = 0
  Q = G.V                    # Q is a min-priority queue
  while Q ≠ ∅
    u = Extract-min(Q)
    for each v ∈ Adj[u]
      if v ∈ Q and w(u, v) < v.key
        v.π = u
        v.key = w(u, v)