0

假设您有一个输入文件：

<total vertices>
<x-coordinate 1st location><y-coordinate 1st location>
<x-coordinate 2nd location><y-coordinate 2nd location>
<x-coordinate 3rd location><y-coordinate 3rd location>
...

Prim 算法如何用于找到这些位置的 MST？我知道这个问题通常使用邻接矩阵来解决。如果适用，任何参考资料都会很棒。

4

2 回答 2

0

如果您已经了解 prim，这很容易。创建邻接矩阵 adj[i][j] = 位置 i 和位置 j 之间的距离

于 2013-04-14T06:22:57.600 回答
0

我只是要描述一些 Prim 的实现，希望能帮到你。

首先，您的问题没有指定如何将边缘输入到程序中。您有顶点总数和这些顶点的位置。你怎么知道哪些是连接的？

假设您有边缘（以及这些边缘的权重。就像上面的@doomster 所说，它可能是点之间的平面距离，因为它们是坐标），我们可以开始考虑我们的实现。维基百科描述了三种不同的数据结构，导致三种不同的运行时间：http ://en.wikipedia.org/wiki/Prim 's_algorithm#Time_complexity

最简单的是邻接矩阵。正如您可能从名称中猜到的那样，矩阵描述了“相邻”的节点。准确地说，有|v|行和列（其中|v|是顶点数）。at 的值adjacencyMatrix[i][j]因用途而异。i在我们的例子中，它是节点和之间的边的权重（即距离）j（这意味着您需要以某种方式索引顶点。例如，您可以将顶点添加到列表中并使用它们在列表中的位置） .

现在使用这个邻接矩阵，我们的算法如下：

  1. 创建一个包含所有顶点并以“距离”为键的字典。最初所有节点的距离是无穷大。
  2. 创建另一个字典来跟踪“父母”。我们使用它来生成 MST。跟踪边缘更自然，但通过跟踪“父母”实际上更容易实现。请注意，如果您将一棵树作为根（即指定某个节点作为根），那么每个节点（除了根）都只有一个父节点。因此，通过制作这本父母词典，我们将拥有我们的 MST！
  3. v使用从原始列表中 随机选择的节点创建一个新列表。
    1. 从距离字典中删除v并将其添加到父字典中，并以 null 作为其父项（即它是“根”）。
    2. 遍历该节点的邻接矩阵中的行。对于任何w已连接的节点（对于未连接的节点，您必须将其邻接矩阵值设置为某个特殊值。0、-1、int最大值等）将其在字典中的“距离”更新为adjacencyMatrix[v][w]. 这个想法是它不再“无限远”了......我们知道我们可以从那里到达v。
  4. 虽然字典不为空（即当有我们仍然需要连接的节点时）
    1. 查看字典并找到距离最小的顶点x
    2. 将其添加到我们的新顶点列表中
    3. 对于它的每个邻居，将它们的距离min(adjacencyMatrix[x][neighbor], distance[neighbor])更新为 并将其父节点更新为x。基本上，如果有更快的方法可以到达，neighbor那么距离字典应该更新以反映这一点；如果我们然后添加neighbor到新列表中，我们知道我们实际添加了哪条边（因为父字典说它的父是x）。
  5. 我们完成了。随心所欲地输出 MST（您需要的一切都包含在父母字典中）

我承认从维基百科页面到上面概述的实际实现有一点飞跃。我认为解决这个差距的最好方法就是暴力破解代码。我的意思是，如果伪代码说“找到最小 [blah] 使得 [foo] 为真”，那么编写执行该操作所需的任何代码，并将其粘贴在单独的方法中。它肯定是低效的，但它会是一个有效的实现。图算法的问题在于有 30 种方法可以实现它们，而且它们的性能都非常不同；维基百科页面只能从概念上描述算法。好消息是，一旦你实施了一些方式，您可以快速找到优化（“哦，如果我在这个单独的数据结构中跟踪这个状态，我可以让这个查找方式更快！”）。顺便说一句，this 的运行时间是O(|V|^2). 我懒得详细分析该分析，但大致是因为：

  1. 所有初始化都O(|V|)更糟
  2. 我们执行循环O(|V|)时间并花O(|V|)时间查看字典以找到最小节点。所以基本上多次找到最小节点的总时间是O(|V|^2)。
  3. 更新距离字典所需的时间是O(|E|)因为我们只处理每条边一次。因为这|E|也是O(|V|^2)O(|V|^2)
  4. 跟踪父母是O(|V|)
  5. 输出树是O(|V| + |E|) = O(|E|)最坏的
  6. 添加所有这些（除了（2）之外，它们都不应该相乘）我们得到O(|V|^2)

堆的实现与O(|E|log(|V|)上面的非常相似。唯一的区别是更新距离O(log|V|)不是O(1)（因为它是一个堆），而是查找/删除 min 元素O(log|V|)而不是O(|V|)（因为它是一个堆）。分析中的时间复杂度非常相似，您最终会得到O(|V|log|V| + |E|log|V|) = O(|E|log|V|)所需的结果。

实际上......我有点困惑为什么邻接矩阵实现关心它是一个邻接矩阵。它也可以使用邻接表来实现。我认为关键部分是如何存储距离。我在上面概述的实现中可能会有所偏离，但我很确定它实现 Prim 的算法满足 wikipedia 概述的时间复杂度限制。

于 2013-04-14T12:14:09.123 回答