连接无向图的算法
和风
抱歉，如果已经有一个问题要问，但是我找不到与此特定问题相关的任何东西。我有一组要从中创建无向连接图的已定义节点。我也有一组连接这些节点的边，但是我不能保证这些边的集合会使图连接起来。我的情况的示例如下所示。
仔细检查会发现，有了边，节点集实际上就是三个图。我想做的是找到一种确定可以添加到边列表中的边的方法，以使其成为一个相连的图。最好是，我想添加尽可能少的边缘（即，我不想通过添加所有可能的边缘来解决问题）。为了增加侮辱性伤害，我不想添加与其他边缘交叉的边缘（每个节点都有定义的位置）。
挣扎地
可以有效地找到连接的组件（例如，如u_seem_surprised所述）。这将列出所有可能的连接链接。不幸的是，这个列表很长-任何一个组件中的任何节点都可以连接到其他任何节点，甚至哪个组件最好连接也不清楚。从这么长的列表中很难找到满足您非交叉需求的链接。
我怀疑对于这种混合问题，没有任何已知的最佳算法。相反，我建议您尝试一些自然的启发式方法。
最好的启发式方法将取决于问题的特征（例如，很少的组件和很多的节点，反之亦然）。但是这是我正在考虑的一种启发式方法的可能示例。
为了找到要在任何两个连接的组件之间链接的节点，我建议您首先尝试从组件A中最接近组件B中质心的节点。我认为可以使用空间索引来有效地做到这一点。然后，您可以再次使用索引尝试将该节点连接到组件B中最近的节点。
检查两个链接是否交叉的算法非常简单。
为了确定要连接的组件，我认为您可以尝试以下操作：
为每个组件的质心创建一个带有节点的新图形。将新的完整网格添加到新图中，链接长度等于质心之间的距离。在此新图上找到这些质心之间的最小生成树。现在，沿着最小生成树连接组件。
但是，此算法可以告诉您连接无法连接的组件（例如，想象一个由三个同心组件组成的图形-您将无法将外部连接到内部）。因此，这只能是启发式建议。
最好始终将一个组件连接到具有最近节点的另一个组件。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
无向图的A *算法
- 2
Dijkstra是针对有向图还是无向图的算法？
- 3
带负边的有向无环图的Dijkstra算法
- 4
本体的图形布局算法（有向无环图）
- 5
将Dijkstra的算法修改为无向图
- 6
无向图和有向图的最小生成树算法有什么区别？
- 7
查找无向图的所有连接组件
- 8
如何输出无向图的所有双向连接的分量？
- 9
在无向图的所有连接的组件的最小要素的总和
- 10
查找有向图的每个弱连接组件的算法
- 11
无向图的着色
- 12
如何查找无向图的所有连接子图
- 13
为无向无权图实现推重贴标签算法st最小割边
- 14
使用字典对无向图上的floyd算法进行图初始化？
- 15
为什么我的Dijkstra在Java中针对无向图的算法实现不起作用？
- 16
查找无向图的程度
- 17
JGraphX中的无向图
- 18
无向图的DFS树
- 19
Cytoscape用于无向图
- 20
无向图的最小ID
- 21
JGrapT 设置无向图
- 22
连通无向无环图与树
- 23
VBA 使有向图无向
- 24
在无向连通图中，如何找到一组顶点以去除哪些图断开连接？
- 25
如何使给定的无向图成为双向连接，并增加最小数量的边？
- 26
查找在第二个图中连接的无向图的顶点
- 27
O（m + n）算法检查有向图是否单边连接
- 28
无向图中的连接组件
- 29
查找距离至少为（无向）图直径一半的任意两个节点的算法
我来说两句