#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?=?{}

????#開始時(shí)候圖中相同的頂點(diǎn)，但沒有邊，賦予每個(gè)點(diǎn)不同的連通分量值
????for?idxnode?in?enumerate（self.MakeComponent（start{}））:
??????nodeSet[node]?=?idx?#nodeSet為node點(diǎn)和其對應(yīng)連通分量的集合

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

????#按權(quán)值