在图中寻找最小循环的算法 [英] 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 或 All-Pairs Shortest Paths 的解决方案，但我无法理解其中任何一个.
我试图实现我在这里找到的 Horton 算法:Horton 算法 但我在第 5 页的第 4 步试图真正找出循环时卡住了.
有人可以向我解释在 Horton 算法的第 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 算法，添加了一些代数.伪代码太大，放在这里，链接如下:

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屋！