如何找到包含给定边的最小生成树？
在加权无向图中，我需要找到一个包含给定边“e”的最小生成树，如果可能的话。我该怎么做呢？Kruskal从“e”开始？
共有1个答案
我不会使用Kruskal算法，因为如果边e是循环的一部分，并且e在该循环中具有最大权值，那么算法将不包括e。我相信只要修改一下，它就能起作用。但是使用Prim的算法所需的修改是最小的。
Prim的算法最适合这个问题，如果我们回忆一下Prim算法是这样的：
步骤1：从包含随机选取的顶点的集合S开始。
第三步：将y添加到设置S。
步骤4：重复步骤2和3直到S包含所有顶点。
需要修改：
对于您的问题，只需将步骤1更改为：
步骤1：从包含顶点u和v的集合S开始，其中边'e'=(u，v)。
-
这是考试准备的一部分。我知道这和最大流量算法有关，但我很乐意给你一个提示： 设为无向连通图，为权函数，为边，。描述一种算法，该算法确定是否可以从图中最多删除边，以便属于新图的最小生成树。 我认为生成树是一种完美的匹配。但是，如何使它最小化，包含e和适当数量的其他边？
-
问题: 给定 N 个节点和 M 条边的图形，边的索引范围为 1 - 你需要为M条边分配权重。权重在[1...M]，并且每个数字只能出现一次。 简而言之，答案应该是[1]的置换数组...M]，其中arr[i] = x表示edge[i]的权重为x。 你得到了一个由n-1条边组成的集合。R保证是图的生成树。 找到一种分配权重的方法，使R是图的最小生成树，如果有多个答案，则打印具有最小字典顺序的答案。 约
-
我试图解决类似于这个问题，但有一些修改： “给定一个值V，如果我们想换V美分，并且我们有无限量的C={C1，C2，…，Cm}值硬币，那么换硬币的最小数量是多少？” 输入：硬币[]={25,10,5}，V=30 输出：至少需要2个硬币 我们可以用一枚25美分的硬币和一枚5美分的硬币 在我的例子中，我有一个对象数组，而不仅仅是一个数字数组。每件物品都有数量和价格。我想打印构成给定数量的最小数量的对象，
-
设T=(V，E)是一棵顶点和边的树，代价已知。我们想构造一个最小权完备图G=(V,E')，它的唯一最小生成树是T。 示例：考虑下面的树T，红色边具有给定的代价。将添加虚线边以从这棵树构造一个完整的图。 作为其唯一MST而跨越T的最小权完备图G如下所示： 2）对MST的所有其他边，权重，按权重递减的顺序重复。进行只包括而不包括其他MST边的切割。此切割的任何未知非MST边的权重应为。 问题： 1）上
-
我现在使用的算法有点问题。我想让它划定界限。 下面是当前行为的一个例子： 以下是一个被通缉行为的示例： C#中凸壳的当前代码：https://hastebin.com/dudejesuja.cs 我的问题是： 1） 这可能吗？ R:是的 2）这甚至被称为凸包吗？（我不这么认为） R：不，这叫边界，link：https://www.mathworks.com/help/matlab/ref/boun
-
我有许多对象需要渲染到画布上。我的输入是轴对齐边界框的有序列表。这些框经常重叠，但也经常在它们之间留下大面积的空白。 我想尽量减少我必须创建的画布表面面积，以便以正确的顺序渲染所有这些项目，而不必在多个画布上渲染单个对象的部分（从而避免简单地创建紧贴所有占用空间的画布）。 所以基本上，我希望紧密的对象组都呈现在同一个画布上，而不重叠的对象应该呈现在单独的画布上。但是，并不是所有重叠的对象都应该呈现