最小生成树之Prim算法和Kruskal算法

时间:2022-11-12 19:38:50

最小生成树算法

一个连通图可能有多棵生成树,而最小生成树是一副连通加权无向图中一颗权值最小的生成树,它可以根据Prim算法和Kruskal算法得出,这两个算法分别从点和边的角度来解决。

Prim算法

理解

Prim算法从单一顶点开始,其按照以下步骤逐步扩大树中所包含顶点的数目,直到遍及连通图的所有顶点。

  1. 输入:一个加权连通图,其中顶点集合为V,边集合为E;
  2. 初始化:Vn = {x},其中x为集合V中的任一节点(起始点),Enew = {};
  3. 重复下列操作,直到Vn = V:
    1. 在集合E中选取权值最小的边(u, v),其中u为集合Vn中的元素,而v则是V中没有加入Vn的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    2. 将v加入集合Vn中,将(u, v)加入集合En中;
  4. 输出:使用集合Vn和En来描述所得到的最小生成树。

以下面这张图作为例子,表格中的Vertex、Kown、Cost、Path分别表示顶点信息、是否访问过,权值,到达路径;

最小生成树之Prim算法和Kruskal算法

我们随机的选择顶点0作为起点,其执行步骤为:

步骤 选中结点
顶点0作为起始点 0
根据(6, 7, 8)的方案选中6 1
根据顶点1能够到达的权值(7, 4, 3)和顶点0能够到达的权值(7, 8)中选择3 5
根据顶点5能够到达的权值(8)和根据顶点1能够到达的权值(7, 4)和顶点0能够到达的权值(7, 8)中选择4 6
根据顶点6能够到达的权值(6, 7)和顶点0能够到达的权值(7)中选择6 2
根据顶点0能够到达的权值(7)和顶点6能够到达的权值(7)中选择7 4
根据顶点6能够到达的权值(7)选择7 7
根据顶点7能够到达的权值(2)选择2 3
全部结点都访问过,退出

最终得到下面的结果,其中Path中的-1表示其作为起始点;

最小生成树之Prim算法和Kruskal算法

实现

根据前面的那幅图来实现,如下:

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算法能够在并查集的基础很快的实现。

以下面这张图作为例子,其中左边的表格是一个并查集,表示可以连通的结点。我们首先要根据权值对每条边进行排序,接着开始处理每一条边的情况。

最小生成树之Prim算法和Kruskal算法

最终得到下面的结果图:

最小生成树之Prim算法和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] else (n1, n2)
union[n2] += union[n1]
union[n1] = n2
res.append(edge)
print(union.values())

其中union打印出来的结果和图中是一致的,为[3, 3, 5, 6, 6, 6, -8, 3]

最小生成树之Prim算法和Kruskal算法的更多相关文章

  1. java实现最小生成树的prim算法和kruskal算法

    在边赋权图中,权值总和最小的生成树称为最小生成树.构造最小生成树有两种算法,分别是prim算法和kruskal算法.在边赋权图中,如下图所示: 在上述赋权图中,可以看到图的顶点编号和顶点之间邻接边的权 ...

  2. 【数据结构】最小生成树之prim算法和kruskal算法

    在日常生活中解决问题经常需要考虑最优的问题,而最小生成树就是其中的一种.看了很多博客,先总结如下,只需要您20分钟的时间,就能完全理解. 比如:有四个村庄要修四条路,让村子能两两联系起来,这时就有最优 ...

  3. 最小生成树之 prim算法和kruskal算法&lpar;以 hdu 1863为例&rpar;

    最小生成树的性质 MST性质:设G = (V,E)是连通带权图,U是V的真子集.如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中, (u,v)的权c[u][v]最小,那么一定存在G的一棵最 ...

  4. 最小生成树(prim算法和kruskal算法)

    学习博客:https://www.cnblogs.com/zhangming-blog/p/5414514.html 其实就是加点法:从不属于这个集合的点中找从本集合可以找到的最小边,加入本集合 看代 ...

  5. 转载:最小生成树-Prim算法和Kruskal算法

    本文摘自:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html 最小生成树-Prim算法和Kruskal算法 Prim算 ...

  6. 最小生成树——Prim算法和Kruskal算法

    洛谷P3366 最小生成树板子题 这篇博客介绍两个算法:Prim算法和Kruskal算法,两个算法各有优劣 一般来说当图比较稀疏的时候,Kruskal算法比较快 而当图很密集,Prim算法就大显身手了 ...

  7. 最小生成树Prim算法和Kruskal算法

    Prim算法(使用visited数组实现) Prim算法求最小生成树的时候和边数无关,和顶点树有关,所以适合求解稠密网的最小生成树. Prim算法的步骤包括: 1. 将一个图分为两部分,一部分归为点集 ...

  8. Prim算法和Kruskal算法

       Prim算法和Kruskal算法都能从连通图找出最小生成树.区别在于Prim算法是以某个顶点出发挨个找,而Kruskal是先排序边,每次选出最短距离的边再找. 一.Prim(普里姆算法)算法: ...

  9. Prim算法和Kruskal算法的正确性证明

    今天学习了Prim算法和Kruskal算法,因为书中只给出了算法的实现,而没有给出关于算法正确性的证明,所以尝试着给出了自己的证明.刚才看了一下<算法>一书中的相关章节,使用了切分定理来证 ...

随机推荐

  1. javascript中字符串的比较规则

    弄清这个还是很重要的,在字符排序中很有用处 非空字符串 > 空字符串 从第一个字符的charCode开始比较,大的就大 所有的字符都相同,就比较长度,长的大 '0'>'' '2'>' ...

  2. 取出type&equals;&quot&semi;button&quot&semi; 和type&equals;&quot&semi;text&quot&semi; 里面的值显示在页面

    <script  type="text/JavaScript> function changeLink() { document.getElementById("nod ...

  3. iOS上百度输入法引起的问题

     /*      UIKeyboardWillShowNotification 通知下的数据            百度     {         UIKeyboardAnimationCurveU ...

  4. hitTest和pointInside和CGRectContainsPoint

    很多app中TabBar中间会有个凸起超出部分,为了点击超出父视图但是还想让按钮响应 //重写hitTest方法,去监听发布按钮的点击,目的是为了让凸出的部分点击也有反应- (UIView *)hit ...

  5. &lbrack;LeetCode&rsqb; Design In-Memory File System 设计内存文件系统

    Design an in-memory file system to simulate the following functions: ls: Given a path in string form ...

  6. Mysql高性能笔记(一)&colon;Schema与数据类型优化

    1.数据类型 1.1.几个参考优化原则 a.  更小的通常更好 i.更小的数据类型,占用更少磁盘.内存和CPU缓存,需要的CPU周期更少 ii.如果无法确定哪个数据类型是最好的,就选择不会超过范围的最 ...

  7. Exception in thread &quot&semi;main&quot&semi; java&period;lang&period;*Error &Tab;at java&period;util&period;ArrayList&dollar;SubList&period;rangeCheckForAdd&lpar;Unknown Source&rpar;

    Exception in thread "main" java.lang.*Error at java.util.ArrayList$SubList.ran ...

  8. 理解Liang-Barsky裁剪算法的算法原理

    0.补充知识向量点积:结果等于0, 两向量垂直; 结果大于0, 两向量夹角小于90度; 结果小于0, 两向量夹角大于90度.直线的参数方程:(x1, y1)和(x2, y2)两点确定的直线, 其参数方 ...

  9. C &lt&semi;string&period;h&gt&semi;常用函数介绍

    1. strcpychar *strcpy(char *destin, char *source);功能:将source指向的字符串拷到destin. int main() { ]; "; ...

  10. Java并发机制和底层实现原理

    Java代码在编译后会变成Java字节码,字节码被类加载器加载到JVM里,JVM执行字节码转化为汇编指令在CPU上执行.Java中的并发机制依赖于JVM的实现和CPU的指令. Java语言规范第三版中 ...