最小生成树

本文收录内容：Kruskal和Prim两个算法，基于Python实现的最小生成树。

最小生成树的背景：$n$个村庄，每个村庄之间只能修一条路，如何使得总路径最短。

• Kruskal从最短的边开始寻找，避免回路，加入$n-1$条边后就是最小生成树。
• Prim是从某个定点出发，定点加入点集$T$，选择与定点相邻距离最短的点加入$T$，并从$T$出发继续寻找，以此类推。

如果对本文有疑问或者想找男朋友，可以联系我，点击此处有我联系方式。

代码如下：

import numpy as np 


class Graph(object):

    def __init__(self, maps):
        self.maps = maps
        self.nodenum = self.get_nodenum()
        self.edgenum = self.get_edgenum()
 
    def get_nodenum(self):
        return len(self.maps)
 
    def get_edgenum(self):
        count = 0
        for i in range(self.nodenum):
            for j in range(i):
                if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
                    count += 1
        return count
 
    def kruskal(self):
        res = []
        if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
            return res
        edge_list = []
        for i in range(self.nodenum):
            for j in range(i, self.nodenum):
                if self.maps[i][j] < 9999:
                    #按[begin, end, weight]形式加入边
                    edge_list.append([i, j, self.maps[i][j]])
        #按照边的权重进行排序
        edge_list.sort(key=lambda a:a[2])
       # 统计每个点有几个
        group = [[i] for i in range(self.nodenum)]

        for edge in edge_list:
            for i in range(len(group)):
                # 边的起点
                if edge[0] in group[i]:
                    m = i
                # 边的终点
                if edge[1] in group[i]:
                    n = i
            if m != n:
                res.append(edge)
                group[n] = group[m] + group[n]
                # m点已经走过，清空，防止下次遍历
                group[m] = []
        return res
 
    def prim(self):
        res = []
        if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
            return res
        res = []
        # 初始第一个点
        seleted_node = [0]
        # 剩余的点
        candidate_node = [i for i in range(1, self.nodenum)]
        
        while len(candidate_node) > 0:
            begin, end, minweight = 0, 0, 9999
            for i in seleted_node:
                for j in candidate_node:
                    if self.maps[i][j] < minweight:
                        minweight = self.maps[i][j]
                        begin = i
                        end = j
            res.append([begin, end, minweight])
            # 加入新的点
            seleted_node.append(end)
            # 删除已添加的点
            candidate_node.remove(end)
        return res
        

if __name__ == '__main__':
	maps = [
	[0, 7, 100, 3, 100, 5], 
	[7, 0, 9, 100, 3, 100], 
	[100, 9, 0, 6, 100, 4],
	[3, 100, 6, 0, 8, 10], 
	[100, 3, 100, 8, 0, 4], 
	[5, 100 ,4, 10, 4, 0]
]	

	graph = Graph(maps)
	print('邻接矩阵为\n%s'%np.array(graph.maps))
	print('节点数据为%d，边数为%d\n'%(graph.nodenum, graph.edgenum))
	print('---------------------Kruskal---------------------')
	print(graph.kruskal())
	print('---------------------Prim------------------------')
	print(graph.prim())

---