c++ - 图组件之间的路径算法

Question

首先，这是一道作业题。我有一个 bool 矩阵，其中 1s 代表节点，相邻节点被认为是连接的。 例如:

1 0 0 0 1
1 1 1 0 0
1 0 0 1 1
0 0 0 0 0
0 0 0 0 0

根据我给出的定义，该矩阵包含 3 个组。一个在左上角，由5个节点组成，一个在右上角，由1个节点组成，下一个由2个节点组成。
我需要做的是编写一个函数来确定必须添加到矩阵中以连接所有单独组件的最少节点数。当可以从一组中的任何节点到另一组中的任何节点建立路径时，两组连接。

所以，我要求有人在算法方面将我推向正确的方向。我已经考虑过如何使用路径查找算法来找到两组之间的最短路径，但不确定如何为矩阵中的每个组执行此操作。如果我使用深度优先遍历来确定单独的组，那么我是否可以对每个组中的任意节点到另一个节点使用路径查找算法？

Answer 1

一般问题称为the Steiner Tree problem , 它是 NP 完全的。

有一种算法不是指数级的，但会为您提供次优解决方案。

您可以这样做的方法是计算任意两对组件之间的最短路径，仅使用初始组件和您计算的权重来构建最小生成树，然后通过您的解决方案并消除循环。

由于您有很多连接岛屿的选项，我会添加一个步骤来优化连接。

但最佳答案的算法:NP-complete(尝试每个组合)。