Kruskal's MST Algorithm in Python

I needed this to create an algorithm that calculates base cycles in a graph. The code requires the disjoint set class from a previous post.

def kruskal_mst(vertices, edges):
  """Kruskal's algorithm that returns edge list of minimum spanning tree.

  For details see:
  http://en.wikipedia.org/wiki/Kruskal's_algorithm

  vertices - a list of the vertex names
  edges - a list of paired tuples representing edges e.g., ('v1', 'v2')

  """
  span = []
  spanAdd = span.append
  data = DisjointDataStruct(vertices)
  for v1, v2 in edges:
    if data.find(v1) != data.find(v2):
      spanAdd((v1, v2))
      data.union(v1, v2)
  return span



Note: This is not a weighted graph implementation. To make it such, have the edges come in with weights as the first value in a tuple triplet. Call edges.sort() after data assignment and make the for statement read:




for w, v1, v2 in edges:

  ...