0

我有一组线段。每个仅包含 2 个节点。我想找到通过连接线段产生的可用闭合循环。实际上，如果存在不止一次，我正在寻找最小的循环。如果可以，请给我一个很好的解决方案。因此，例如，我在下面的行列表中添加了它们的点索引，以了解 m 案例。（其中第一个值 = 行号，第二个 2 值是点索引）

0 - 9 11  
1 - 9 18  
2 - 9 16  
3 - 11 26  
4 - 11 45  
5 - 16 25
6 - 16 49  
7 - 18 26 
8 - 18 25  
9 - 18 21  
10 - 25 49  
11 - 26 45

所以，假设我从第 1 行开始。也就是说，我已经开始从第 9 点、第 18 点开始找到连接的循环。那么，你能否解释一下（一步一步地）我如何从那条线上获得“闭合循环”。

4

1 回答 1

1

好吧，我没有看到任何 C++ 代码，但我会尝试建议一个 C++ 解决方案（尽管我不会为你编写它）。

如果您的图是无向的（如果它是有向的，s/adjacent/in-edges' vertices/），并且您想找到通过某个顶点 N 的所有最短循环，那么我认为您可以遵循以下过程：

G <= a graph
N <= some vertex in G
P <= a path (set of vertexes/edges connecting them)
P_heap <= a priority queue, ascending by distance(P) where P is a path

for each vertex in adjacent(N):
  G' = G - edge(vertex, N)
  P = dijkstraShortestPath(vertex, N, G')
  push(P, P_heap)

您也可以只丢弃除最短循环之外的所有循环，但这不那么简洁。只要您不允许负边权重（因为您将使用线段长度作为权重，所以您不允许），我认为这应该可行。此外，幸运的是，Boost.Graph 提供了在 C++ 中执行此操作所需的所有功能（您甚至不必实现 Dijkstra 的算法）！您可以在此处找到有关它的文档：

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html

编辑：您必须先从您首先列出的数据创建图表，然后才能执行此操作，因此您只需相应地定义图表的 property_map 并确保您要插入的顶点与当前所有顶点之间的距离图形大于零，否则顶点已经在图形中，您不想再次插入它。

快乐的绘图！

于 2011-09-27T18:28:31.813 回答