最小生成树_为什么要求最小生成树_sophistcxf的博客-程序员秘密

一、什么叫最小生成树

一个无向连通图G=(V,E)，最小生成树就是联结所有顶点的边的权值和最小时的子图T，此时T无回路且连接所有的顶点，所以它必须是棵树。

二、为什么要研究最小生成树问题

《算法导论》上举了电子线路设计的例子。而在经济学、生物学中也常应用最小生成树。

三、如何求一个无向连通图的最小生成树

《算法导论》中提取讲解了两种得到最小生成树的算法，一是Kruskal算法，另一种是Prim算法。这两种算法都使用了贪心策略。

先说明几个概念：

安全边：A是G的某最小生成树的子集，如果AU{(u,v)}仍是G的某最小生成树的子集，则(u,v)是安全边；

割：无向图G=(V, E)对V一个划分(S, V-S)；

边(u,v)通过割(S,V-S)：(u,v)一个顶点位于S中，另一个顶点位于V-S中；

不妨害A的割：A中没有任意一条边通过该割；

轻边(light edge)：通过割的所有边中权值最小的（可能有多条）。

生成最小生成树的基本代码结构是：

GENERIC-MST(G, w)
    A=空集
    while A does not form a spanning tree
        do find an edge(u,v) that is safe for A
            A=AU{(u,v)}
    return A

于是关键就在于找安全边。

定理（《算法导论》中定理23.1）（以白话阐述）：G=(V,E) 是个无向连通加权图。A 是 E 的一个子集，它包含于 G 的某个最小生成树中。设割 (S, V-S) 是G的任意一个不妨害A的割（就是说A中任何一条边的两个端点要么全在S中，要么全在V-S中），边(u,v)是通过割（S,V-s)的一条轻边（就是说(u,v)是所有端点分布于S和V-S的边中权值最小的），则(u,v)对集合A是安全的。

推论：A是G=（V,E)的某个最小生成树的子集。G(A)=(V,A)是图G的一个森林（只有A集合中的边），C=（Vc, Ec)为G(A)的一个连通分支（森林中的树）。如果边(u,v)是连接C和G(A)中其他某连通分支的一条轻边，则(u,v)对集合A来说是安全的。

1. Kruskal 算法

MST-KRUSKAL(G, w)
    A=空集
    for each vertex v∈V[G]
        do MAKE_SET(v)
    sort the edges of E into nondescreasing order by weight w
    for each edge(u,v)∈E, take in nondescreasing order by weight
        do if FIND-SET(u) != FIND-SET(v)                              // 如果u和v不在同一个连通分支中，就把(u,v)加入，由推论可知此边是安全的
            then A = AU{(u,v)}
                UNION(u,v)
    return A

FIND-SET(u)是找出u所在的连通分支。

Kruskal在全局中找权值最小的边，然后判断此边是否“合法”，进行取舍，直到遍历完所有的边。

Kruskal算法的运行时间为O(ElgV)。

2. Prim算法

MST-PRIM(G, w, r)
    for each u∈V[G]
        do key[u]=∞
          π(u) = NIL     // π(u)是u的前趋
    key[r] = 0
    Q=V[G]
    while Q != 空集
        do u=EXTRACT-MIN(Q)
            for each v∈Adj[u]
                do if v∈Q and w(u,v)<key[v]
                    then π(v)=u
                          key[v] = w(u,v)       // 更新key[v]

Q是一个优先队列，key[v]是所有将v与树中某一顶点相连的边中的最小权值，若不存在这样的边，则k[v]=∞。

Prim算法在局部寻找权值小的的边（此边必合法），直到遍历完所有的节点。

Prim算法的运行时间为O(ElgV)，与Kruskal算法渐近相等。

Prim算法实际上使用了与Dijkstra算法同样的策略，维护了一个权值数组key，在迭代过程中不断的更新。

本文链接：https://blog.csdn.net/sophistcxf/article/details/9164521

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Vue 2.0使用sass_vue 2.0项目中使用sass_Faith_ZL的博客-程序员秘密

如何在Vue 2.0中使用sass在项目中使用sass，less等css预处理器语言方便我们更快捷高效的开发。但是在Vue 2.0cli安装sass的时候会报错。最终已经解决，现在贴出我的解决方法。首先安装所需的模块。npm i node-sass style-loader [email protected]安装sass-loader的时候一定要指定版本，如果sass的版本太高，webp...

element ui里面table分页,页数从0开始的怎么做？_weixin_30321449的博客-程序员秘密

需求:后台请求的接口是从0页开始的,但是pagination是从1开始的,就是在点击pagination的第1页是后台转01首先在data里面定义为1,其他地方也是定义1 return { formSearch: { name: '', phone: '', page: 1, size: 10 }}2...

移动端地区选择的插件_234u.cc_qq_33645229的博客-程序员秘密

今天我分享的是一个地区选择器，这是我找到的看着样式什么的挺不错，推荐下，这是样式html部分&lt;div class="content-block"&gt; &lt;input id="demo1" type="text" readonly="" placeholder="地区" value=""/&gt; &

[email protected]修饰方法形参[email protected] 修饰参数_不想做咸鱼的咸鱼的博客-程序员秘密

当使用@ModelAttribute修饰方法形参，这意味着该参数值会自动绑定成Model属性归纳一下，SpringMVC可以从下面三个地方获取参数值：同名请求参数同名的路径变量名同名的model属性栗子：用户请求url：/my?name=lyx&age=22"/test/2"控制器：@Controllerpublic class UserController{ @GetMapping("/my") //从同名的请求参数中获取方法参数 //在这

Python面向对象2_ljy0291的博客-程序员秘密

继承的概念单继承多继承子类重写父类同名的属性和方法子类调用父类同名的属性和方法多层继承通过super（）调用父类方法（扩展）程序中的继承在程序中，继承描述的是多个类之间的所属关系。如果一个类A里面的属性和方法可以复用，则可以通过继承的方式，传递到类B里。那么类A就是基类，也叫做父类；类B就是派生类，也叫做子类。 # 父类 class A(object): def __init__(self): self.num = 10 def print_...

Php中方法作用域,php的类中五种字段作用域_慕栗子的博客-程序员秘密

1.public 表示修饰的字段的作用域范围是公共作用域该作用域的字段可以在类外部直接通过对象名访问,并进行修改.实例一:class deyushe{public $name;public $address;}$dys = new deyushe();$dys -> name = "德予舍";$dys -> address = "www.deyushe.com";printf("网站名...