关于在 Boruvka 算法中执行下一步的问题
A question about performing the next step in Boruvka's Algorithm
我对实现 Boruvka 的最小生成树算法有疑问。
假设我们有下图：
如何找到每个 node/vertex 中最小的 connection/edge 对我来说相当简单明了。
我的问题是关于您如何执行下一步。
据我了解，在 Boruvkas 算法中，您执行遍历所有组件并通过组件自身最轻的连接将组件与另一个组件组合的操作。在上图中，这意味着将组件 {0} 和 {1} 合并为一个组件（我们称之为组件 {0,1}）以及将组件 {2} 和 {3} 合并为组件 {2,3} .所以我们的组件列表从 {{0},{1},{2},{3}} 到 {{0,1},{2,3}}。在执行此操作时，我们还将连接这些组件的边保存在一个单独的列表中。在第一步结束时，形成最小生成树的边列表如下所示：{2,2}
我的问题：我怎样才能将 {0} 和 {1} 变成一个组件并执行下一步？假设在执行第一步后我有一个更大的图和以下组件：{{0,1,2,3,4,5},{6,7,8,9,10}}。在这个阶段我到底要做什么？我是否必须查看将它连接到任何顶点的 0 - 5 的所有边
6 - 10 并选择最轻的一个？
How exactly can I turn {0} and {1} into a single component
首先，您将连接边添加到边的解决方案集中。挑战在于（在算法期间）了解任何一对节点是否属于同一组件。有几种方法可以做到这一点。一种是使用 disjoint set，也称为 union-find。
...and perform the next step? Assume I have a larger graph and the following components after performing the first step: {{0,1,2,3,4,5},{6,7,8,9,10}}. What exactly do I do at this stage? Do I have to look through all the edges of 0 - 5 that connect it to any vertex from 6 - 10 and choose the lightest one?
您必须查看在第一个分量 (0 - 5) 中具有一个节点的所有边：仅考虑那些连接到 不是 [= 的节点的边19=]在同一组件中，取最轻的一个。
我对实现 Boruvka 的最小生成树算法有疑问。
假设我们有下图：
如何找到每个 node/vertex 中最小的 connection/edge 对我来说相当简单明了。 我的问题是关于您如何执行下一步。
据我了解，在 Boruvkas 算法中，您执行遍历所有组件并通过组件自身最轻的连接将组件与另一个组件组合的操作。在上图中，这意味着将组件 {0} 和 {1} 合并为一个组件（我们称之为组件 {0,1}）以及将组件 {2} 和 {3} 合并为组件 {2,3} .所以我们的组件列表从 {{0},{1},{2},{3}} 到 {{0,1},{2,3}}。在执行此操作时，我们还将连接这些组件的边保存在一个单独的列表中。在第一步结束时，形成最小生成树的边列表如下所示：{2,2}
我的问题：我怎样才能将 {0} 和 {1} 变成一个组件并执行下一步？假设在执行第一步后我有一个更大的图和以下组件：{{0,1,2,3,4,5},{6,7,8,9,10}}。在这个阶段我到底要做什么？我是否必须查看将它连接到任何顶点的 0 - 5 的所有边 6 - 10 并选择最轻的一个？
How exactly can I turn {0} and {1} into a single component
首先，您将连接边添加到边的解决方案集中。挑战在于（在算法期间）了解任何一对节点是否属于同一组件。有几种方法可以做到这一点。一种是使用 disjoint set，也称为 union-find。
...and perform the next step? Assume I have a larger graph and the following components after performing the first step: {{0,1,2,3,4,5},{6,7,8,9,10}}. What exactly do I do at this stage? Do I have to look through all the edges of 0 - 5 that connect it to any vertex from 6 - 10 and choose the lightest one?
您必须查看在第一个分量 (0 - 5) 中具有一个节点的所有边：仅考虑那些连接到 不是 [= 的节点的边19=]在同一组件中，取最轻的一个。