Kruskal算法python实现

#encoding=utf-8
import networkx
from matplotlib import pyplot
from collections import defaultdict
#a b 7
#a d 5
#b c 8
#b d 9
#b e 7
#c e 5
#d e 15
#d f 6
#e f 8
#e g 9
#f g 11
def Edge（）: return defaultdict（Edge）
class Graph:
  def __init__（self）:
    self.link = Edge（）
    self.FileName = ‘‘
    self.Separator = ‘‘

  def Makelink（selffilenameseparator）:
    self.FileName = filename
    self.Separator = separator
    graphfile = open（filename‘r‘）
    for line in graphfile:
      items = line.split（separator）
      self.link[items[0]][items[1]] = int（items[2]）
      self.link[items[1]][items[0]] = int（items[2]）
    graphfile.close（）
    
  def MakeComponent（selfnodevisited）:
    visited[node] = True
    component = [node]
    for neighbor in self.link[node]:
      if neighbor not in visited:
        component += self.MakeComponent（neighborvisited）  
    return component
    
    
  def Kruskal（selfstart）:
    graphEdges = [line.strip（‘‘）.split（self.Separator） for line in open（self.FileName‘r‘）]              
    nodeSet = {}

    #开始时候图中相同的顶点，但没有边，赋予每个点不同的连通分量值
    for idxnode in enumerate（self.MakeComponent（start{}））:
      nodeSet[node] = idx #nodeSet为node点和其对应连通分量的集合

    edgeNumber = 0; totalEdgeNumber = len（nodeSet）-1

    #按权值