标签: minimum-spanning-tree

我可以使用什么算法在有向图上找到最小生成树？我尝试使用Prim算法的修改,但无法使其工作.

我有一个无向连通图G.我希望找到一个算法,如果至少有2个MST,则返回true.

如果我想查看是否有2个MST,该怎么办？

Dijkstra通常用于查找图中两个节点之间的最短距离.它可以用来找到最小生成树吗？如果是这样,怎么样？

编辑:这不是作业,但我试图理解旧练习考试的问题.

我花了很多时间阅读有关最小生成树的剪切属性的在线演示和教科书.我并没有真正得到它的假设,甚至为什么它是实用的.据说它有助于确定要添加到MST的边缘,但我没有看到它是如何实现的.到目前为止,我对cut属性的理解是你将MST分成两个任意子集.这里有什么帮助？谢谢!

我正在研究Prim的算法.代码中有一个部分,切割的下一个顶点将会到达属于该顶点的顶点集MST.在这样做的同时,我们还必须"更新另一组中与离开顶点相邻的所有顶点".这是来自的快照CLRS:

有趣的部分在于行号.11.但是由于我们在这里使用堆,我们只能访问最小元素right(heap[0])？那么我们如何从堆中搜索和更新顶点,即使它们不是最小的顶点,因此除了线性搜索之外我们知道它们在哪里？

我正在研究图论,我对最小生成树和最短路径树之间的联系有疑问.

设G是一个无向连通图,其中所有边都以不同的成本加权.令T为G的MST,并且让T _s为某个节点s的最短路径树.是牛逼和牛逼_小号保证至少有一项优势？

我相信这并非总是如此,但我找不到反例.有没有人有关于如何找到反例的建议？

给定带有加权边的有向图,可以使用什么算法给出具有最小权重的子图,但允许从图中的任何顶点移动到任何其他顶点(假设任何两个顶点之间的路径始终存在) .

这样的算法存在吗？

假设您有一个非负整数边长的有向图,其范围在0到U-1之间.计算此图的最小生成树的最快算法是什么？我们仍然可以使用现有的最小生成树算法,例如Kruskal算法O(m log n))或Prim算法(O(m + n log n)).但是,对于U很小的情况,我认为应该可以做得更好.

是否存在与更传统的MST算法竞争的算法,这些算法能够利用边长被约束在某个范围内的事实？

谢谢!

我正在尝试解决与Python中的图形相关的问题.由于它是一个敏感的编程问题,我没有使用任何其他第三方软件包.

该问题呈现出5 X 5方形网格形式的图形.假设机器人位于网格上的用户提供位置.网格的索引位于(0,0)左上角和(4,4)右下角.网格中的每个单元格由以下3个字符中的任何一个表示.' b'(ascii值98)表示机器人的当前位置,' d'(ascii值100)表示脏单元格,' - '(ascii值45)表示网格中的清洁单元格.例如,下面是机器人所在的示例网格0 0:

b---d
-d--d
--dd-
--d--
----d

目标是以最少的步骤清理网格中的所有单元格.步骤被定义为任务,其中i)机器人改变它的位置ii)机器人改变单元格的状态(从d到 - )

假设最初标记为b不需要清洁的位置.允许机器人向上,向下,向左和向右移动.

我的方法

我已经阅读了几个关于图形的教程,并决定将图形建模为25 X 25的邻接矩阵,0代表无路径,1代表矩阵中的路径(因为我们只能在4个方向上移动).接下来,我决定将Floyd Warshell的所有对最短路径算法应用于它,然后总结路径的值.但我觉得它不起作用.我正处于一个delimma中,问题是以下任何一个问题:

i)最小生成树(我无法做到,因为我无法将网格建模并存储为图形).

ii)A*搜索(同样是一个疯狂的猜测,但这里的问题相同,我无法正确地将网格建模为图形).

如果你能对这些问题提出一个好的方法,我会感激不尽.此外,关于各种形式的基于图形的问题(或链接到那些)的一些提示和伪代码将是有帮助的.谢谢

我正在尝试使用Prim算法实现随机生成的迷宫.

我希望我的迷宫看起来像这样:

但是我从我的程序生成的迷宫看起来像这样:

我目前坚持正确实现以粗体突出显示的步骤:

1. 从充满墙壁的网格开始.
2. 选择一个单元格,将其标记为迷宫的一部分.将单元格的墙添加到墙列表中.
3. 虽然列表中有墙:
   • **1.从列表中选择一个随机墙.如果对面的细胞尚未进入迷宫:
     • 1. 使墙成为通道,并将对面的单元标记为迷宫的一部分.**
     • 2. 将单元格的相邻墙添加到墙列表中.
   • 2. 从列表中删除墙.

从 这篇关于迷宫生成的文章.

如何确定单元格是否是墙列表的有效候选者？我想改变我的算法,以便产生正确的迷宫.任何有助于我解决问题的想法都将不胜感激.