无向图的最小生成树---克鲁斯卡尔算法

"""
克鲁斯卡尔算法：
一种按权值递增顺序选择合适的边来构造最小生成树的算法
关键点：
如何判断选取的边是否与生成树已保留的边形成了回路，可以通过判断边的两个顶点所在的连通分量的方法来解决
设置一个辅助数组vset[0..n−1], 它用于判定两个顶点之间是否连通。数组元素vset[i](初值为i)代表序号为i的顶点所属的连通顶点集的编号
(当选中不连通的两个顶点间的一条边时，它们分属的两个顶点集合按其中的一个编号)。当两个顶点的集合编号不同时，
加入这两个顶点构成的边到最小生成树时一定不会形成回路。
1.将自己指向自身
2.每个集合中的所有节点都指向同一个节点
3.如果两个节点有共同的父节点，那么说明这两个节点所在的边将构成闭环
"""


class DisJointset(dict):
   def __init__(self, _):
      pass

   def add(self, item):
      """
      指向本身
      """
      self[item] = item

   def find(self, item):
      """
      查找远古父节点
      """
      # 如果不是远古父节点，即自己指向自己，那么一直往上寻找
      # 在向上寻找的同时，将寻找过的父节点都指向远古父节点，可以将时间复杂度从O(n)降低为O(1)
      if self[item] != item:
         self[item] = self.find(self[item])
      # 返回父节点
      return self[item]

   def unionset(self, item1, item2):
      """
      合并两个集合，将一个集合的远古父节点与另一个合并，就相当于合并两个集合了
      :param item1: 节点
      :param item2: 节点
      """
      self[item2] = self[item1]


def kruskal(nodes, edges):
   # 创建对象，传入的nodes没有意义，仅仅是继承dict需要而已
   forest = DisJointset(nodes)
   # 加入最小生成树中的边的集合
   MST = []
   # 将各个节点都指向本身
   for item in nodes:
      forest.add(item)
   # 排序
   edges = sorted(edges, key=lambda x: x[2])
   # 边的条数是节点的个数-1时，所有的节点就都加入了树中
   num_sides = len(nodes) - 1
   # 遍历每一条边
   for e in edges:
      # 取出两个节点，权值可以不用管
      node1, node2, _ = e
      # 分别找到两个节点的远古父节点
      parent1 = forest.find(node1)
      parent2 = forest.find(node2)
      # 如果两个父节点不相同，表示node1和node2不在一个集合中
      if parent1 != parent2:
         # 添加数据
         MST.append(e)
         # 数量-1
         num_sides -= 1
         if num_sides == 0:
            return MST
         else:
            # 如果父节点不相同，就合并集合
            forest.unionset(parent1, parent2)


if __name__ == '__main__':
   # 节点信息
   nodes = set(list('ABCDEFGHI'))
   # 边信息
   edges = [
      ("A", "B", 4), ("A", "H", 8),
      ("B", "C", 8), ("B", "H", 11),
      ("C", "D", 7), ("C", "F", 4),
      ("C", "I", 2), ("D", "E", 9),
      ("D", "F", 14), ("E", "F", 10),
      ("F", "G", 2), ("G", "H", 1),
      ("G", "I", 6), ("H", "I", 7)
   ]

   print(edges)
   print(kruskal(nodes, edges))