algorithm - 如何以最短的方式连接所有连接的组件

Question

给定一个由 0 和 1 组成的 N*M 数组。湖是一组水平或垂直相邻的单元 (1)。我们将通过将一些单元格（0）更新为 1 来连接地图上的所有湖泊。任务是找到在给定时间限制内更新单元格数量最小的方式。

我发现了这个类似的问题：连接所有岛屿的最低成本是多少？ 这个主题的解决方案有一些问题：
1）它使用lib（pulp）来解决任务
2）需要时间才能得到输出

有没有针对这个问题的优化解决方案

先感谢您

标签： algorithm

Answer 1

我认为这是一个棘手的问题，但如果你真的把它画出来并将这个矩阵看作一个图表，它就会变得更简单。将每个单元格视为一个节点，并将其顶部/右侧/底部/左侧的每个连接视为一条边。首先将湖泊的边缘连接到附近的顶点。继续对每个顶点执行相同的操作，如果不创建循环，则仅连接两个顶点。在这个阶段，对湖泊的近邻进行相同的处理。继续做同样的事情，如果它的创建周期中断。在此之后，您应该有一个连接的树。

一旦你有一个连接的树，你可以找到树的所有关节点（切割顶点）。（无向连通图中的一个顶点是一个连接点（或切割顶点），如果移除它（和通过它的边）会断开连接图。连接点表示连接网络中的漏洞——其故障会将网络分成 2 或更多断开的组件）

树中切割顶点的数量（不包括初始湖泊）将是您需要更改的最小单元数。

您可以搜索有许多有效的方法来查找图的切割顶点。寻找关节点需要 O(V+E) 预处理需要 O(V+E)，因为它有点类似于 BFS。