Prim 算法 "closest array"

Question

我一直在尝试了解最小跨度树及其相关算法，即 Prim 算法、Kruskal 算法和 Dijkstra 算法。

我了解这些算法是如何工作的，也看到了它们的实际应用，但只有一件事我不了解 Prim 的算法，这是一个数组，我不明白它的意图是什么以及它是如何工作的有用。

情况是这样的：

我必须做一个练习，其中给定一个邻接关系 table 并且我必须运行 Prim 的算法来创建最小跨度树。

table 看起来像这样：

   0 |1|2| 3| 4| 5|
0| 0 73 4 64 40 74 
1| 73 0 46 26 30 70 
2| 4 46 0 77 86 14 
3| 64 26 77 0 20 85 
4| 40 30 86 20 0 22 
5| 74 70 14 85 22 0

以“|”分隔的数字是顶点， table 中的数字是边。很简单，我运行算法（在本网站中例如： http://www.jakebakermaths.org.uk/maths/primsalgorithmsolverv10.html ）或者只是将其记在纸上并绘制最小跨度树，我得到最小成本为 86 的树，并且已使用的边为 4、26、20、22 和 14。

现在问题来了，显然仅仅解决还不够。我需要找到名为 closest[0,...,5] 的数组的值。我知道它在算法中使用，但我不知道它的用途以及我应该用它做什么或如何获得它的值。

我在互联网上搜索了一下，找到了关于 Prim 算法的link： http://lcm.csa.iisc.ernet.in/dsa/node183.html

将数组 "closest" 定义为 "For i in V - U, closest[i] gives the vertex in U that is closest to i".

我还是不明白它是什么，它的用途是什么，里面的值是什么。

我只知道我的练习答案是

closest[1] = 3
closest[2] = 0
closest[3] = 4
closest[4] = 5
closest[5] = 2

提前致谢。

Answer 1

在使用 Prim 算法进行 MST 时，重要的是要跟踪四件事：顶点、它是否被访问过、到顶点的最小距离以及该顶点之前的内容（这就是您要查找的内容） .

您从顶点 0 开始，您会看到离 0 最近的顶点是 2。同时，您可以访问所有其他节点，但距离更大。然而，最接近 0 的节点是 2，因此 2 被访问并且其父节点设置为顶点 0。所有其他节点尚未访问，但其父节点 as of now 是设置为 0，与其各自的距离。现在需要设置要访问的顶点的最小距离，现在把这个节点作为要考虑的节点。

Vertex | Visited | Distance | Parent
0      | T       | -        | -
1      | F       | 73       | 0
2      | T       | 4        | 0
3      | F       | 64       | 0
4      | F       | 40       | 0
5      | F       | 74       | 0

然后我们检查所有节点到 2 的距离。我们将 2 到其他节点的新距离与它以前的距离与其他节点的距离进行比较，如果需要更新，则更新.我们现在看到从 2 到 5 的距离比 0 到 5 更短，顶点 5 现在变为已访问，其父节点现在等于顶点 2。

Vertex | Visited | Distance | Parent
0      | T       | -        | -
1      | F       | 46       | 2
2      | T       | 4        | 0
3      | F       | 64       | 0
4      | F       | 40       | 0
5      | T       | 14       | 2

现在我们访问5。需要注意的是，如果访问了一个节点，我们在距离计算中不考虑它。我已经模拟了其余的，希望你能看到你是如何得到你正在寻找的答案的。

Vertex | Visited | Distance | Parent
0      | T       | -        | -
1      | F       | 46       | 2
2      | T       | 4        | 0
3      | F       | 64       | 0
4      | T       | 22       | 5
5      | T       | 14       | 2

现在访问4

Vertex | Visited | Distance | Parent
0      | T       | -        | -
1      | F       | 46       | 2
2      | T       | 4        | 0
3      | T       | 20       | 4
4      | T       | 22       | 5
5      | T       | 14       | 2

现在访问 3

Vertex | Visited | Distance | Parent
0      | T       | -        | -
1      | T       | 26       | 3
2      | T       | 4        | 0
3      | T       | 20       | 4
4      | T       | 22       | 5
5      | T       | 14       | 2

Prim 算法 "closest array"

Prim's algorithm "closest array"

arrays

prims-algorithm