目录

最小生成树

克鲁斯卡尔算法

普里姆算法

---

最小生成树

对于有n个节点的无向连通图，无论其生成树的形态如何，所有的生成树必然没有回路，而且都有且仅有n-1条边。当无向连通图是一个带权图，其所有生成树中必有一颗边的权值总和最小的生成树，称为最小生成树。

最小生成树有两个算法：

克鲁斯卡尔（Kruskal）算法

普里姆（Prim）算法

克鲁斯卡尔算法

所有权值从小到大排序，顶点集合的有哪些，然后根据权值的小的优先进行排序，不进行回路。

最后实例：

#coding=utf-8
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:
                    edge_list.append([i, j, self.maps[i][j]]) #按[begin, end, weight]形式加入
        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[m] = group[m] + group[n]
                group[n] = []
        return res
max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = Graph(maps)
print('邻接矩阵为\n%s'%graph.maps)
print('节点数据为%d，边数为%d\n'%(graph.nodenum, graph.edgenum))
print('------最小生成树kruskal算法------')
print(graph.kruskal())

程序运行示意图：

普里姆算法

找一个顶点，然后找与此结点相连中间权值最小的结点选择，以此类推。如果到了没有结点可以访问的，或者是都是访问过的，则回到上一个或者是上几个，在已经访问了的节点中间还有没访问的结点，在这些没访问的几点中间找到权值相对于没访问的较小的权值进行访问。

最后实例：

#coding=utf-8
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 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
max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = Graph(maps)
print('邻接矩阵为\n%s'%graph.maps)
print('节点数据为%d，边数为%d\n'%(graph.nodenum, graph.edgenum))
print('------最小生成树prim算法')
print(graph.prim())