草庐IT

第十五章 最小生成树

叶梓渔 2023-03-28 原文

第十五章 最小生成树

定义

生成树：无向图中，包含所有定点在内的极小连通子图

最小生成树：

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称

最小生成树问题：

  • A Generic Algorithm

  • 具有贪心选择性：

    • Kruskal's Algorithm
    • Prim's Algorithm

最小生成树需具备的条件：

  1. Tree is an acyclic（无环），connected(连通、无向) graph.

  2. A tree of |V| vertices has |V| - 1 edges.

  3. 并且任何两个顶点存在unique（唯一的）路径

  4. 增加任何一条边都会使得树形成回路，如果去掉任何一条边，就会使得该树不再连通

问题

输入：一个连通带权无向图G(V，E；W)

输出：一个最小生成树T for G

方法

A Generic Algorithm

  • 每次生成最小生成树的一条边：须遵循，在一次循环之前，集合A已经是最小生成树的子集的原则
  • 安全边：A如果加上{（u，v）}这条边和相关顶点以后仍然构成最小生成树的子集，则称这条边为安全边

求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。

当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。

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 <- A ∪ {(u,v)}
	return A
  • 如何判断边是否安全？
    • 例：u∈S，v∈V-S，则（u，v)是否安全？
    • 例：u，v∈S，则（u，v)是否安全？
    • 解答：集合S，集合V-S同属于集合V，则S与V-S两集合间的最短距离，假设两集合间存在这条边（u，v)，则必然有u∈S，v∈V-S。如果边（u，v)的权值是跨越割集的所有边中最小的，我们就称这条边是当前来讲可选的最轻的一条边，而且是一条安全边。能够跨域割集的边是安全边，能够构成子集的一定是所有跨越中最小的

​ Kruskal's Algorithm是从边出发，寻找（安全）边；Prim's Algorithm是从点出发，寻找（安全)边

如图，{a,b,d,e}∈S，{c,i,h,g,f}∈V-S， 则（c,d)是一条安全边

Kruskal's Algorithm

初始A是一个森林，每一个加入A的安全边应该总是权值最小的连接两个不同点的边。

  1. 初始化每个顶点都是单独一棵树，即有n个集合，每个集合有一个元素。A<-∅

  2. 在森林中任意两棵树之间找一棵权值最小的安全边(u,v) //需对所有边的权值进行排序

  3. 将（u，v)加入到A并合并这两棵树变成一棵树。

  4. Repeat step 2 and 3 until A forms a spanning tree.(直到找到n-1条边)

Prim's Algorithm

初始A是一棵树，每次加入到A的安全边总是连接A和A之外某个结点的权值最小的边。

  1. 从任意一个结点r出发，把r加到顶点集合U中，U初始为空集
  2. 找到最小权值边（u，v)，u∈U，v∈V-U，把边（u，v)加入到A，把v加入到U
  3. Repeat 2 until A forms a spanning tree or U = V.

问题

  • key[u] 保存的是连接点u和树中结点的所有边中最小边的权重
  • Π[u] u的父节点
第十五strongliAlgorithm算法与数据结构

有关第十五章 最小生成树的更多相关文章

  1. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  2. ruby - 返回空白页的最小 Capybara/Poltergeist 测试 - 2

    看来我正在回顾SO帖子中采取的步骤:Capybara,PoltergeistandPhantomjsandgivinganemptyresponseinbody.(如果你愿意，可以将其标记为重复，但我包含了一个最小的独立测试用例和版本号。)问题我做错了什么吗？我可以运行另一个可能有助于隔离问题的最小测试吗？文件:pgtest.rbrequire'rubygems'require'capybara'require'capybara/dsl'require'capybara/poltergeist'modulePGTestincludeCapybara::DSLextendselfdeft

  3. ruby - 寻找产品和商店的最佳组合以最小化成本的算法 - 2

    你好，Stackoverflow的人们，我经营一个网站，为用户寻找最便宜的书籍购买地点。这对于单本书来说很容易，但对于多本书来说，有时在一家商店购买一本书而在另一家商店购买另一本书会更便宜。目前我找到了销售用户列表中所有书籍的最便宜的商店，但我想要一个更智能的系统。这里有更多信息:一本书的价格对于一家商店来说是不变的。运费可能会有所不同，具体取决于书籍的数量或书籍的总值(value)。每个商店对象都可以获取一组书籍并返回运费。通常，并非每家书店都出售每一本书。不确定在这里链接到我的站点是否很酷，但它列在我的用户配置文件中。我希望能够找到最便宜的商店和书籍组合。我担心这需要一种蛮力方法-

  4. 用于进行线性或非线性最小二乘近似的 Ruby 库？ - 2

    是否有Ruby库允许我对一组数据进行线性或非线性最小二乘法逼近。我想做的是:给定一系列[x,y]数据点针对该数据生成线性或非线性最小二乘法近似值库不必弄清楚它是否需要进行线性或非线性近似。库的调用者应该知道他们需要什么类型的回归我不想尝试移植某些C/C++/Java库来获得此功能，因此我希望有一些现有的Ruby库可供我使用。 最佳答案 尝试使用“statsample”gem。您可以使用下面提供的示例执行对数、指数、幂或任何其他转换。我希望这有帮助。require'statsample'#IndependentVariablex_da

  5. ruby-on-rails - 如何在 Rails 3 的表格列中找到最小值 - 2

    嗨，假设我有一个table(ads)，其中有一个column(views)观看次数21463如何找到该列中的最小值？有什么简单的方法可以做到这一点？这就是我的@ads=Ad.all@show_this_ad=@ads.min(:views)这给了我一个“参数数量错误(1代表0)错误”@ads=Ad.all@show_this_ad=@ads.minimum(:views)这给了我一个“未定义的方法错误” 最佳答案 Ad.minimum(:views)应该可以您仍然可以添加更多限制，例如:Ad.where(:user_id=>1234

  6. ruby - 在 Ruby 中获取整数数组的最小公倍数 - 2

    我知道，在Ruby中，您可以使用Integer#lcm求两个数的最小公倍数的方法。例如:10.lcm(15)#=>30是否有一种有效的(或内置于核心或标准库中)方法来获取给定数组中所有整数的最小公倍数？例如:[5,3,10,2,20].lcm#=>60 最佳答案 任何需要两个操作数的操作都可以通过folding迭代地应用于一个集合它:Enumerable#inject/reduce.为了覆盖空情况，将identityelement作为第一个参数传递操作的最小公分母为1。[5,3,10,2,20].reduce(1){|acc,n|a

  7. Ruby:如何找到最小数组元素的索引？ - 2

    有什么办法可以更优雅地重写这个吗？我认为，这是一段糟糕的代码，应该重构。>>a=[2,4,10,1,13]=>[2,4,10,1,13]>>index_of_minimal_value_in_array=a.index(a.min)=>3 最佳答案 我相信这只会遍历数组一次并且仍然很容易阅读:numbers=[20,30,40,50,10]#=>[20,30,40,50,10]elem,idx=numbers.each_with_index.min#=>[10,4] 关于Ruby:如何找

  8. ruby - 如何使用 Ruby 找到最小值/最大值 - 2

    我想使用min(5,10)或Math.max(4,7)。Ruby中有实现这种效果的函数吗？ 最佳答案 你可以做到[5,10].min或[4,7].max它们来自Enumerablemodule，因此任何包含Enumerable的内容都将具有可用的方法。v2.4引入了自己的Array#min和Array#max，它们比Enumerable的方法快得多，因为它们跳过调用#each.@nicholasklick提到了另一个选项，Enumerable#minmax,但这次返回一个[min,max]数组。[4,5,7,10].minmax=>

  9. javascript - 与用户操作交互的模态弹出窗口，如用户设置的最大化、最小化、关闭、调整大小和可拖动 - 2

    我需要与用户操作交互的模态弹出窗口，如下图所示。但是这个模态弹出窗口应该是纯java脚本。严禁使用JQuery或JQuery插件。期待您的来信。提前致谢。 最佳答案 这里我分享一些插件，基本上都是用Jquery和Javascript创建的。无论您在纯JavaScript中寻找什么，都可以使用http://alpha.jspanel.de/media/demos/nojquery/index.php另一个是使用Jquery创建的。是https://lobianijs.com/site/lobipanel#examples使用第一个选项

  10. 使用 Genie 效果最小化 <div> 的 Javascript？ - 2

    这个问题不太可能帮助任何future的访问者；它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关，这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用，visitthehelpcenter.关闭10年前。我想最小化一个框，就像Mac上Sprite效果中的弹出窗口一样，我找到了jQueryTransfereffect很接近，但还不够，它只画了一个轮廓，并没有真正涂抹物体，有没有办法模仿Mac的Sprite最小化效果？谢谢。

随机推荐