minimum-spanning-tree

0热度

1回答

任何人都可以解释我为什么下面不工作的代码，并返回我 W = [.34 .34 ]; DG = sparse([1 2],[2 3],W); UG = tril(DG + DG') ???使用==>错误加上矩阵尺寸必须一致。下面的代码能正常工作吗？ W = [.34 .34 .34]; DG = sparse([1 2 3],[2 3 1],W); UG = tril(DG + D

3热度

3回答

证明，没有最小生成树包含最大加权边缘

比方说，有图G，使得它的所有边缘都对应于不同的整数权重。所以没有两个边缘具有相同的重量。设E是G的所有边。令emax为E中具有最大权重的边。 Graph G的另一个性质是每条边e属于G中的某个循环。我必须证明没有G的最小生成树包含边emax。我不得不证明G的最小生成树不包含边emax。我明白为什么这是真的，因为所有的边是不同的，每边属于一个周期，最小生成树算法可以简单地选择边缘与包含EMAX周

1热度

1回答

使用Prim算法从O（n^3）到O（n^2）优化MST

以下是我使用Prim算法将连通图转换为MST的伪代码。然而，我得到了n^3的复杂度，而不是n^2。请帮我弄清楚不需要的步骤。我有一个邻接矩阵“a”来存储图边的权重，一个2D矩阵“检查”存储树中已经存在的顶点“1”，其余的为“0”。请注意，这也可以在nlog（n）中完成，但我不想引用任何现有的伪代码，并希望自己尝试。我将不胜感激优化我自己的方法的答案。 Initialize check. //ch

0热度

2回答

最小产品生成树是否与最小生成树不同？

最小产品生成树是否与最小生成树不同？ PLZ解释（如果可能的话，用示例）。我的意思是，添加到最小值的边应该（？）也具有最小的乘积。

0热度

1回答

为MCST分配缺少的边缘成本

我在解决旧的考试试卷时遇到了这个问题。根据所给出的选项，我几乎不知道如何解决这个问题。考虑以下无向图ģ一些边成本丢失。假设虚线刃形成最小成本从生成树（MCST）ģ。那么下列哪个不等式需要而不是持有？成本（A，B）≥6 成本（B，E）≥5 成本（E，F）≥5 成本（A，d）≥4 成本（b，c）≥4

0热度

2回答

有没有什么办法可以快速找到无向/有向图中的一个周期（后沿）的所有边？

我有一个最小生成树。我为它添加了一个边缘。当然会形成一个循环。我需要找到作为该周期一部分的所有边，即所有后边。可以做多快？我的解决方案 - 例如，如果它是边缘（1,4），请在所有位置向Adj（1）添加4，然后每次运行dfs。例如。如果Adj（1）有2,3,5，则在2之前先加4，运行DFS。我会得到回报。然后在2和3之间添加4并运行dfs。我得到了另一个后端。然后在3和5之间等等。有没有更快的方法来

2热度

1回答

java中最小生成树（邻接矩阵）

我有一个问题，我真的很苦恼。我有一组边缘重的村庄，我需要创建一棵最小生成树来找到最短路径。我已经根据重量找到了村庄的最短路径，我真的不知道该怎么做我该如何执行这与邻接矩阵？我会感谢任何帮助:) -10个村庄（节点）

3热度

1回答

C++如何实现秩定理双重量（而不是整数）

我发现使用Kruskal算法的最小生成树模板here 他们使用整数重量，是可能的，如果我要实现的代码使用双重重量？我在这里和那里做了更改，并一直给我错误。这是我改变了：和 double myComp(const void* a, const void* b) { struct Edge* a1 = (struct Edge*)a; struct Edg

-3热度

1回答

如何将Dijkstra算法应用到我的邻接图？

我有一个编程任务，需要我建立一个邻接图并应用Dijkstra算法来找到一个MST。我已经构建了我的邻接图，但是我不知道如何将伪代码应用于Dijkstra算法。链接曾经为Dijkstra算法为邻接表的代码，http://www.cs.utsa.edu/~wagner/CS3343/newgraph/graphrep.html 伪代码： http://i.imgur.com/TtPARzW.png

0热度

2回答

图形可视化

我写了一个java程序，用随机生成的100个顶点和随机生成的800个边来计算最小生成树。我想绘制一下当我运行它时该程序生成的图形。有谁知道任何工具，可以帮助这个？下面我的Java代码： public static void main (String [] args) { Random random = new Random(); Edge[] edges = new Ed