算法查找最小周期中的曲线图 [英] Algorithm for finding minimal cycles in a graph

问题描述

我在寻找，鉴于它返回所有的最小周期在它的图形算法。
为了清楚我想要什么，我需要的算法，从该图中正好返回以下循环：
 （1,3,6,1），（1,6,4,1），（1,4,2,1），（6,4,7,6），（2,4,7,2）， （2,7,5,2）

I'm looking for an algorithm that given a graph it returns all the minimal cycles in it.
To make clear what I want, I need the algorithm to return exactly the following cycles from this graph:
(1,3,6,1), (1,6,4,1), (1,4,2,1), (6,4,7,6), (2,4,7,2), (2,7,5,2)

我一直在寻找了很多，我仍然无法弄清楚这个问题连名字。难道是周期的基础问题，或者根本周期问题，或者是这两个相同的？ 我发现涉及MST或全偶最短路径解决方案，但我不明白任何人。
我试图执行霍顿的算法，我在这里找到：霍顿的算法但我被困在第5页试图真正找出周期中的第4步。
有人可以给我解释一下究竟需要在霍顿的算法的第4步完成或者给我另一种算法来解决我的问题？

I've been searching alot and I still can't figure out even the name of this problem. Is it the cycle basis problem or the fundamental cycles problem or are those two the same? I found solutions involving MST or All-Pairs Shortest Paths but I can't understand any of them.
I tried to implement Horton's algorithm which I found here: Horton's Algorithm but I got stuck at the 4th step in page 5 trying to actually find out the cycles.
Can somebody either explain to me what exactly needs to be done in step 4 of Horton's algorithm or give me another algorithm to solve my problem?

推荐答案

本文主要介绍几何工具库中使用算法（写入IC C ++，我认为）。它基本上是与另外一些代数的修改DFS算法。伪code是往大了它张贴在这里，所以这里是链接：

This paper describes algorithm used in geometric tools library (written ic C++ i think). It's basically a modified DFS algorithm with addition of some algebra. The pseudocode is to big to post it here, so here is the link:

http://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf

我目前工作的JavaScript实现。如果你有兴趣，你可以在这里查看：

I'm currently working on javascript implementation. If you're interested you can view it here:

http://jsbin.com/igujuz/8/edit

这篇关于算法查找最小周期中的曲线图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！