|
最小生成树算法 一个连通图可能有多棵生成树,而最小生成树是一副连通加权无向图中一颗权值最小的生成树,它可以根据Prim算法和Kruskal算法得出,这两个算法分别从点和边的角度来解决。 Prim算法理解 Prim算法从单一顶点开始,其按照以下步骤逐步扩大树中所包含顶点的数目,直到遍及连通图的所有顶点。 1、输入:一个加权连通图,其中顶点集合为V,边集合为E; 2、初始化:Vn = {x},其中x为集合V中的任一节点(起始点),Enew = {}; 3、重复下列操作,直到Vn = V: 在集合E中选取权值最小的边(u, v),其中u为集合Vn中的元素,而v则是V中没有加入Vn的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一); 将v加入集合Vn中,将(u, v)加入集合En中; 4、输出:使用集合Vn和En来描述所得到的最小生成树。 以下面这张图作为例子,表格中的Vertex、Kown、Cost、Path分别表示顶点信息、是否访问过,权值,到达路径;  我们随机的选择顶点0作为起点,其执行步骤为:  最终得到下面的结果,其中Path中的-1表示其作为起始点;  实现 根据前面的那幅图来实现,如下: class MST(object): def __init__(self, graph): self.graph = graph self.N = len(self.graph) pass def prim(self, start): index = start cost, path = [0] * self.N, [0] * self.N #初始化起点 known = [x for x in map(lambda x: True if x == start else False, [x for x in range(self.N)])] path[start] = -1 for i in range(self.N): cost[i] = self.graph[start][i] #遍历其余各个结点 for i in range(1, self.N): mi = 1e9 #找出相对最小权重的结点 for j in range(self.N): if not known[j] and mi > cost[j]: mi, index = cost[j], j #计算路径值 for j in range(self.N): if self.graph[j][index] == mi: path[index] = j known[index] = True #更新index连通其它结点的权重 for j in range(self.N): if not known[j] and cost[j] > self.graph[index][j]: cost[j] = self.graph[index][j] print(path) #图用临接矩阵表示 MST([ [1e9, 6, 8, 1e9, 7, 1e9, 1e9, 1e9], [6, 1e9, 7, 1e9, 1e9, 3, 4, 1e9], [8, 7, 1e9, 1e9, 1e9, 1e9, 6, 1e9], [1e9, 1e9, 1e9, 1e9, 1e9, 1e9, 1e9, 2], [7, 1e9, 1e9, 1e9, 1e9, 1e9, 1e9, 1e9], [1e9, 3, 1e9, 1e9, 1e9, 1e9, 1e9, 9], [1e9, 4, 6, 1e9, 1e9, 1e9, 1e9, 7], [1e9, 1e9, 1e9, 2, 1e9, 9, 7, 1e9], ]).prim(0) path结果为:[-1, 0, 6, 7, 0, 1, 1, 6] Kruskal算法理解 构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树的根节点,则它是一个含有n棵树的森林 。之后,从图的边集中选取一条权值最小的边,若该边的两个顶点分属不同的树 ,则将其加入子图,也就是这两个顶点分别所在的 两棵树合成一棵树;反之,若该边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林只有一棵树。kruskal算法能够在并查集的基础很快的实现。 以下面这张图作为例子,其中左边的表格是一个并查集,表示可以连通的结点。我们首先要根据权值对每条边进行排序,接着开始处理每一条边的情况。  最终得到下面的结果图:  实现 因为我们要处理边,所以需要建立边的数据结构,并且要从给定的图中获取每一条边的数据 class Edge(object): def __init__(self, start, end, weight): self.start = start self.end = end self.weight = weight def getEdges(self): edges = [] for i in range(self.vertex): for j in range(i+1, self.vertex): if self.graph[i][j] != 1e9: edge = Edge(i, j, self.graph[i][j]) edges.append(edge) return edges 接下来就是kruskal函数: def kruskal(self): union = dict.fromkeys([i for i in range(self.vertex)], -1) # 辅助数组,判断两个结点是否连通 self.edges = self.getEdges() self.edges.sort(key=lambda x: x.weight) res = [] def getend(start): while union[start] >= 0: start = union[start] return start for edge in self.edges: #找到连通线路的最后一个结点 n1 = getend(edge.start) n2 = getend(edge.end) #如果为共同的终点则不处理 if n1 != n2: print('{}----->{}'.format(n1, n2)) (n1, n2) = (n2, n1) if union[n1] <> union[n2] += union[n1] union[n1] = n2 res.append(edge) print(union.values()) 其中union打印出来的结果和图中是一致的,为[3, 3, 5, 6, 6, 6, -8, 3]  有钱任性,某公司豪掷500万帮助20左右年轻人找工作,起因是做善良的人: http://www./zt/jyfc/?wt.bd=zdy35845tt 学安卓,免学费!50天兴趣课程等你来抢! http://www./xydt/2017/13042.html?wt.bd=zdy35845tt IT职业教育:http://xue./ |
|
|
