1回答
聚类最小生成树的数据集
、、、
最近我遇到了最小生成树的概念，发现它在聚类中有一个应用程序。我正在寻找一个真实的数据集(最好是干净的)，它可以作为各种聚类算法的数据源。有一种信息表明，MST聚类在球面和非球面数据上工作得足够好。这就是为什么非球面数据集也被追求的原因。
我心目中的数据集应该包含地面真相信息(标签)，因此各种标志的有效性可以通过与WSS不同的东西来衡量。
浏览 1提问于2018-06-12得票数 0
回答已采纳
1回答
我需要根据它们的余弦相似性来聚类(假设作为参数k)，单词(我存储在数组列表中)。我已经将我所有的单词作为顶点存储在一个完整的、加权的、无向图(使用邻接列表)中，并将它们的余弦相似度值放在边上。据我所知，我需要使用MST (Kruskals算法)进行聚类处理。
然而，由于我的图是完全图，而MST用于连通图，我有点困惑如何在完全图上使用它？还是我用完全图做错了？
这是我的wordList：
[directors, producers, film, movie, black, white, man, woman, person, man, young, woman, science, fictio
浏览 2提问于2018-04-28得票数 0
回答已采纳
1回答
最短路径练习
、、、、
我正在尝试解决以下问题：
我们的银河系里有N颗行星。你可以在不同的行星之间旅行，但并不是每个行星都通过一条安全的路线连接到另一个行星。每条路线都有一个以光年为单位的给定长度。您的任务是在给定的一组行星T(其中0
输入包括N(行星数量)、R(行星之间安全路线的数量)、三元组A B L形式的R路径，其中A和B表示行星的恒星in，L表示它们之间的距离(以光年为单位)，T(需要建立基地的行星的数量)，后跟表示需要建立基地的行星的in的T数字。
您总是从ID为0的行星开始。在行星0上建立基地可能需要也可能不需要。
我试着解决了这个练习，并设法得到了一个有效的解决方案，但它太慢了。我使用弗洛伊德·沃肖尔算
浏览 3提问于2015-04-07得票数 1
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 但我不知道是否应该从K个节点进一步到另一个节点。尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
2回答
考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？
浏览 4提问于2020-03-29得票数 0
1回答
正如维基百科所说：
最小生成林是其连通部分的最小生成树的结合。
为了找到最小生成树，我们可以使用例如、或。
我们可以用什么算法来寻找最小生成森林？
浏览 2提问于2017-05-16得票数 2
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。
我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的距离)。
通过这种方式，我只是购买更长更细的电缆，这是一种更便宜的解决方案，较短，较厚的电缆。
浏览 1提问于2013-06-27得票数 6
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
带度约束的最小生成树
、、、、
我必须解决这个问题：
给出了一个加权连通无向图G=( V，E)和顶点u，给出了求G的MST的算法，使得u的度最小，算法的输出T为最小生成树T‘，最小生成树T’为T中u小于或等于u在T‘中的度。
我考虑了这个算法(在googling搜索之后，我找到了类似问题的解决方案)：
临时删除顶点u。
对于每个得到的连接组件C1，…，Cm使用例如Kruskal或Prim的算法找到MST。
重新添加顶点u，并为每个词添加1和Ci之间最便宜的边。
编辑：
我知道这个算法可能会产生错误的MST (见@AndyG注释)，所以我想到了另一个：
设k是G中每两个权重之间的最小增量，并将0
浏览 10提问于2015-05-17得票数 2
回答已采纳
1回答
我得找出堵车的降雨门槛。
所以，我必须打印降水的阈值来阻止交通。
(前)
3 3
0 1 2
1 2 3
0 2 6
产出:3
对于这个问题有什么好的算法或关键字吗？
谢谢
浏览 0提问于2019-04-02得票数 1
回答已采纳
如果最小生成树是贪婪的，为什么Kruskal的算法会找到它呢？最小生成树不是一个全局优化问题吗？贪婪的意义不是在于你有可能找不到最优的解决方案吗？那么，Kruskal如何在贪婪的情况下找到最小生成树呢？
浏览 2提问于2016-12-10得票数 5
1回答
加权有向图的Prim算法
、、、
我在学习最小生成树。我研究了Prim关于加权有向图的算法。
算法简单
您有两个顶点集，已访问的和未访问的。
将所有边的距离设为无穷远
从未访问集中的任意顶点开始，并探索其边缘。
在所有边缘中，如果目标顶点没有被访问，并且如果边缘的权重小于目标顶点的距离，则使用该边缘的权重更新目标顶点的距离。
选择距离最小的未访问顶点，然后再做一次，直到所有顶点都被访问。
通过上述算法，我可以在所有的生成树中找到代价最小的生成树，即最小生成树。
但是我把它应用到下面的例子中，我认为它失败了。
请考虑以下示例
顶点是{v1，v2，v3，v4，v5}和带权的边。
(x，y)：W
浏览 2提问于2014-03-18得票数 0
7回答
如何找到最大生成树？
、、、
与Kruskal的最小生成树算法相反的算法对它有效吗？我的意思是，选择每一步的最大权重(边)？
有没有找到最大生成树的其他想法？
浏览 4提问于2011-02-14得票数 64
回答已采纳
1回答
我需要得到一个完整图的MST，其中所有的边都默认为权重3，而且我还得到了有权重1的边。
下面是一个例子
5 4 (N, M)
1 5
1 4
4 2
4 3
Resulting MST = 3 -> 5 -> 1 -> 4 -> 2
如果第一行有总节点数(N)，则1权重边(M)的数量和以下所有行(M)都包含权重为1的边。
我试着构造一个完整的图并将给定边的权值更新为1，但是对于一个包含10^5 1权边的问题来说，空间复杂度太大了。
浏览 4提问于2021-11-28得票数 1
回答已采纳
1回答
我正在阅读一本算法教科书，以提高我的算法技能，但我在这个问题上完全被困住了，这让我很困扰。我认为底层的数据结构是一个图表，但我甚至不知道从哪里开始这个问题。有人能给点见解吗？谢谢
给出了一个地形图，该地形图提供了任意两个相邻城市和两个城市a和b之间的直接道路上的最大高度。提出了一个线性时间算法，该算法可以找到从s到t的路径，从而使最大高度最小化。道路可以双向通行。
浏览 3提问于2013-10-01得票数 1
我可以使用什么算法来解决这样的问题：
有一个图的正权重，我想知道每个节点连接的权重的最小和(像网络一样连接，其中每个节点是一个eg。网络设备)。
在这个网络中，每个节点都可以通过其他节点以某种方式与其他节点相连。但输入图中的所有节点都必须位于网络中。
浏览 1提问于2010-04-26得票数 0
回答已采纳
1回答
在加权图中将循环图转换为无圈图
、、、、
我得到了一个具有非负权重的连通加权图。我想把它转换成一个连通的非循环图，这样被移除的边的权重之和就会最小化。输出将是移除的边。 我的想法是:由于一个连通的非循环图是一棵树，我可以简单地获取最大的n-1边，然后删除所有其他边。但是，这并不总是正确的。它可能导致不连通的图。 然后，我想到了使用dfs。我知道如何使用dfs检测图是否有圈，但我不知道如何检测涉及到的所有边，以及如何将其转换为非循环图。任何帮助(代码/伪代码/文字中的算法)都将不胜感激。谢谢..。
浏览 36提问于2019-06-12得票数 1
回答已采纳
3回答
有谁能解释为什么Kruskal产生的树与Dijkstra不同？
我知道kruskal工作在边的非降序上，但是Dijkstra利用优先级队列，但仍然不明白为什么从它们得到的树是不同的？
浏览 2提问于2013-12-05得票数 7
回答已采纳
3回答
新闻文章聚类
、、、、
我的场景非常简单:我有一堆新闻文章(目前约1k篇)，我知道其中一些报道了相同的故事/主题。我现在想根据共享的故事/主题对这些文章进行分组，即基于它们的相似性。
到目前为止，我所做的是应用基本的NLP技术，包括去停用词和词干提取。我还计算了每一篇文章的tf-idf向量，并可以根据这些tf-idf向量计算余弦相似度。但现在，随着文章的分组，我有点挣扎了。我看到了两种主要的方法--可能是相关的--来做到这一点：
1)机器学习/集群:我已经使用了一些现有的集群库，或多或少取得了成功；请参阅。一方面，像k-means这样的算法需要输入聚类的数量，我不知道。其他算法需要的参数也不是很直观(对我来说是这样)
浏览 1提问于2014-08-10得票数 14
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器。
我找不到任何方法来求出所有生成树的权重，而且生成树的数目也可能很大，所以这种方法可能不适合这个问题。由于最小生成树的数目是指数的，将它们计算起来不是一个好主意。
所有的重量都是正数。
我们还可以假设，在图中不会出现超过三次的权重。
顶点的数目将小于或等于40,000。
边数将小于或等于100,000。
图中只有一个最小生成树，其中顶点的权重是不同的。我
浏览 4提问于2012-12-13得票数 9
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。
我用Prim算法找到了最小生成树。。
我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树吗？
浏览 1提问于2019-03-17得票数 0
回答已采纳
当我找到一个“临界边缘”问题的解决方案时，我遇到了这个问题。我已经解决的最初(C++)问题是：
考虑一个图G=(V，E)。找出有多少边属于所有的 MST，有多少边不属于属于任何MST，有多少边属于一些MST，但不是全部。
让我们分别将“绿色”、“红色”和“黄色”称为上述3种情况下的边缘。
在进行我的研究之后，我偶然发现了，它解决了这个问题。一个将运行Kruskal算法的修改版本:如果两个或多个相同权重的边缘连接相同的组件，从而形成一个循环，那么所有这些都是黄色边缘，即可以包含在MST中的边缘(或不包括)。无可争辩地被选中的边缘是“绿色”的，在同一组件中创建循环的边缘是“红色”的。原来的
浏览 3提问于2014-12-31得票数 4
回答已采纳
我不确定如何处理这个问题。
给定一个无向图，每条边的颜色不是红色就是蓝色。如何在时间复杂度(O(m + n) log )内找到包含尽可能少红色边的最小生成树。其中m个顶点和n个是边。
任何帮助都将不胜感激。
浏览 1提问于2015-12-07得票数 1
假设我们有一个问题，其中有几个城市之间的路径成本(在时间上)是可变的，并且我们有两个推销员，他们两个之间必须至少访问每个城市一次。
现在，假设我们有一个算法，给定一个推销员和一组城市，可以为这个推销员设计一条最优路径。我们想要做的是以这样的方式划分城市，将一套分配给第一个推销员，另一套分配给另一名推销员，这样我们就可以得到一个解决方案，使总时间尽可能地短。做这件事的好方法是什么？我们想要一个很好的解决方案，但不一定是最优的。
我的想法是，我们可以使用某种启发式方法来确定给定的拆分是好是坏，但有很多城市，所以选择拆分是困难的。我不完全确定该怎么做。
需要澄清的是:每个城市必须至少有一个推销员到访
浏览 1提问于2014-05-01得票数 0
Kruskal算法在每次迭代时选择最小的边。虽然最终的目标是获得一个MST，但是解决的子问题是什么呢？是为了让森林有最小的重量，也是完全连接起来的吗？
浏览 5提问于2020-07-03得票数 1
回答已采纳
2回答
我是最小生成树的新手，并试图找出在任何特定情况下使用哪种MST算法。有没有人能举几个例子，说明哪种MST算法比其他算法更合适
浏览 3提问于2013-01-04得票数 2
回答已采纳
1回答
我们如何找到最小化节点v度的最小生成树(在所有最小生成树中)？
修改Kruskal算法，如果有几条边具有相同的权重，我们会选择不接触v的那条边来解决问题吗？
浏览 14提问于2017-02-22得票数 2
1回答
图中有N个点，每个点都有一条到其他(N-1)点的路径，代价为(例如，成本是线距离或曼哈顿距离)。
对于任何点A、B、C，都有两个约束：
成本(A->B) <=成本(A->C)+成本(C->B)
成本(A->B) ==成本(B->A)
现在，我想要做的是找到探索图中所有点的最短路径。方法是什么？或者没有一个推动这个问题的方法。
我有一个想法，假设A是起点，我们尝试从A找到最近的点(假设它是B)，然后我移动到B点。我再次尝试从B找到最近的点(现在A被删除)，直到我探索所有的点。
浏览 5提问于2015-03-22得票数 0
1回答
我正在学习MST算法。我很好奇想要找到prims和boruvka算法之间的关键区别，但在线资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是很大的帮助。谢谢!
浏览 4提问于2021-07-18得票数 2
2回答
首先，请注意，这个问题是而不是询问MST，而只是all possible spanning trees。
所以这是，而不是，与或一样
我只需要从一个图表中生成所有可能的spanning trees。
我认为蛮力的方式是直接的：
假设我们有V节点和E边。
获取图的所有边
将V-1的所有可能组合从E边缘提取出来。
从组合中筛选出non-spanning-tree (对于生成树，一组V-1边缘中的所有节点都应该出现一次)
但是我觉得面对大图的时候太慢了。
我们有更好的方法吗？
浏览 4提问于2014-03-02得票数 9
回答已采纳
1回答
任意无向加权图的反馈集是边的子集，在去除子集中的边后，剩下的图是无圈的。
给定G= (V，E)，一个无向加权图和一个整数k，我如何确定是否有一个总权重不超过k的反馈集？
谢谢!
浏览 5提问于2020-03-17得票数 0
回答已采纳
4回答
最小生成树子图
、、、、
我正在阅读我的书中的所有练习，准备下周复习一次课堂考试，我真的对这个子图问题感到困惑。
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。就目前情况而言，我有点不知所措。
如果X‘的节点集和边集分别是X的节点集和边集的子集，则X’是图X的子图。设(V，T)是G的最小生成树，G‘=(V’，E‘)是G的连通子图。
(a)证明了(V‘，E’∩T)是G‘的最小生成树的子图.
(b)在什么条件下(V‘，E’∩T)是G‘的最小生成树？证明你的主张。
提前谢谢！
浏览 2提问于2012-10-29得票数 4
回答已采纳
1回答
如何将Dijkstra算法应用于图，以使生成的树在两个给定顶点之间必须有一条边？(例如: MST必须包含X和Y之间的边)
谢谢
浏览 2提问于2011-06-01得票数 1
回答已采纳
算法设计手册中的练习
6-10。4.设G= (V，E)是无向图。一个边的集F⊆E称为反馈边集，如果G的每个圈在F (b)中至少有一个边，设G是一个带正边权的加权无向图。设计了一种有效的求最小权反馈边缘集的算法.
我建议的解决方案(b)是运行DFS，获得最大重量作为平局断路器。然后，每一个后边缘将始终是其周期中的最低加权边。我想知道这是否是一个有效的解决方案。
浏览 0提问于2014-11-05得票数 1
给定一个无向加权图，边的实际权重是未知的；相反，每条边都被分类为轻、中或重。
所有轻边的权重都小于任何中边或重边。
所有中边的权重都比任何重边小。
通常，对于同一权重类中的两条边之间的关系一无所知。那么，如何识别这个图的每个MST中必须存在的所有边？以下是我的想法: 1.确定强连通分量的数量。2. MST中必须存在由铰接点组成的边。3.每个连接组件中最亮的边必须存在于MST中。
我不确定我的想法是否正确？如果是正确的，如何用java实现代码？非常感谢。
浏览 1提问于2018-10-20得票数 1
我正在做我的研究，并继续问一个问题：
我有一个最小生成树(prim算法)，现在我的树中的一个节点被删除了，我想知道是否有一种方法可以重新组织我的树，使它仍然保持最优性？
我在这里寻求一些建议，我将感谢你的帮助。
谢谢!
注:所有边权值为1(单位图)。
浏览 0提问于2011-03-23得票数 6
5回答
通常用于查找图中两个节点之间的最短距离。它能用来找出最小的吗？如果是这样的话，是怎么做的？
编辑:这不是家庭作业，但我正在尝试理解一个旧的练习考试中的一个问题。
浏览 5提问于2009-12-16得票数 20
回答已采纳
假设您使用Kruskal或Prim的算法来计算第一个MST，您希望检查是否还有其他的MST。我可以在O(E/V)时间内做到这一点。
该算法使用了一个优先级队列(可以用O(N)构造)。Kruskal和Prim已经使用优先级队列，但它们比下面列出的线性时间算法慢。
我知道已经有一些算法可以在线性时间内找到单个MST：
随机算法可以在线性期望时间内求解。Karger，Klein和Tarjan，“寻找最小生成树的随机线性时间算法”，J. ACM，第42卷，1995年，第321-328页。
当权值为小整数时，可在线性最坏情况下求解。弗雷德曼和威拉德，“最小生成树和最短路径的跨-二重算法”，第31
浏览 2提问于2013-12-20得票数 0
回答已采纳
2回答
我正在使用对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？
浏览 3提问于2013-08-17得票数 1
1回答
当图有多个连通分量时，我不知道如何实现Kruskal算法
根据我对Kruskal算法的理解，它多次向集合中添加最小边。然后，当所有的边都被检查时，它会返回一组最充分的边。
但是，如果我的图是断开的呢？说我有：
A - B - C - D
E - F
假设成本( are )=成本(E)= 1，其余的边大于1。
当我运行Kruskal时，我会得到所有的边的成本，但是我想得到每个连接组件的成本，所以我对所有连接的组件做了一个平均最小的成本。
浏览 0提问于2014-03-07得票数 3
1回答
算法：
图表：
(注:缺边权，(T，Y，8))
在第一次迭代之前：
最小优先级队列(启动时的最小键)
Q= (S，0)，(T，∞)，(X，∞)，(Y，∞)，(Z，∞)
迭代1：
U=S
Q= (T，6)，(Y，7)，(X，∞)，(Z，∞)
更新T和Y的键
迭代2：
U=T
Q= (Z，-4)，(X，5)，(Y，7)
更新X，Y，Z的键
迭代3：
U=Z
Q= (X，5)，(Y，7)
没有更新
迭代4：
U=X
Q= (Y，7)
没有更新
迭代5：
U=Y
Q= []
没有更新
队列为空，循环终止
我们的最小生成树中有以下几个边：
(S，T，6)，(T，Z，5)，(T，Z，-4)，(
浏览 3提问于2017-04-14得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
