最小生成树kruskal算法python实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最小生成树kruskal算法python实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2496字，纯文字阅读大概需要4分钟。

内容图文

#File Name : 最小生成树kruskal算法.py
#思路 边权重从小到大排序 从权重小的边开始
#不形成回路就要，不然不要。直至包含所有点

#File Name : 并查集.py

# 并查集结构
from heapq import  *
class Node(object):
    pass
class UnionFindSet(object):
    def __init__(self,nodes):
        self.fatherDict = {}
        # key node  value father 一层一层向上找
        self.sizeDict = {}
        # key 节点  value 节点所在集合共有多少个节点
        for node in nodes:
            self.fatherDict[node]= node
            self.sizeDict[node] = 1
        #每个节点的父亲是自己 并且所在的集合为个数为1
        #因为要少挂多 ，所以要找节点数目
    def FindHead(self,node):
        stack = []
        father = self.fatherDict[node]
        while father!=node:
            stack.append(node)
            node = father
            father = self.fatherDict[node]
        while stack:
            self.fatherDict[stack.pop()] = father
        return father
    def isSameSet(self,a,b):
        return self.FindHead(a) == self.FindHead(b)
    def uion(self,a,b):
        if a is None or b is None:
            return
        aHead = self.FindHead(a)
        bHead = self.FindHead(b)
        if aHead!=bHead:
            asize = self.sizeDict[aHead]
            bsize = self.sizeDict[bHead]
            if asize<=bsize:
                self.fatherDict[aHead] = bHead
                self.sizeDict[bHead] = asize+bsize
            else:
                self.fatherDict[bHead] = aHead
                self.sizeDict[aHead] = asize+bsize

class Node(object):
    def __init__(self,value=None):
        self.value = value #节点的值
        self.come = 0 #节点入度
        self.out = 0 #节点出度
        self.nexts = [] #节点的邻居节点
        self.edges = [] #在节点为from的情况下，边的集合
class Edge(object):
    def __init__(self,weight=None,fro,to):
        self.weight = weight # 边的权重
        self.fro = fro # 边的from节点
        self.to = to #边的to节点
    def __lt__(self, other):
        return self.weight<other.weight
class Graph(object):
    def __init__(self):
        self.nodes = {} #图所有节点的集合  字典形式 ：{节点编号：节点}
        self.edges = [] #图的边集合

def creatGraph(matrix):
    # 二维数组matrix [权重  从那个点的值  去哪个点的值]
    graph = Graph()
    # 建立所有节点
    for edge in matrix:
        weight = edge[0]
        fro = edge[1]
        to = edge[2]
        if fro not in graph.nodes:
            graph.nodes[fro] = Node(fro)
        if to not in graph.nodes:
            graph.nodes[to] = Node(to)
    #建立所有的边
        fromNode = graph.nodes[fro]
        toNode = graph.nodes[to]
        newEdge = Edge(weight,fromNode,toNode)
        fromNode.nexts.append(toNode) #加上邻居指向
        fromNode.out+=1 #出度+1
        toNode.come+=1 #to 的入度+1
        fromNode.edge.append(newEdge) #边的集合+1
        graph.edges.append(newEdge)

    return graph
#k算法  堆结构  并查集结构  图结构
def kruskalMST(graph):
    unionfind = UnionFindSet(graph.nodes.values())
    heapq = []
    for edge in graph.edges:
        heappush(heapq,edge)
    res = []
    while len(heapq)>0:
        edge = heappop(heapq)
        if unionfind.isSameSet(edge.fro,edge.to)==False:
            res.append(edge)
            unionfind.uion(edge.fro,edge.to)
    return res

 

内容总结

以上是互联网集市为您收集整理的最小生成树kruskal算法python实现全部内容，希望文章能够帮你解决最小生成树kruskal算法python实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---