gpt4 book ai didi

algorithm - 在有向图中查找所有循环

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:11:13 26 4
gpt4 key购买 nike

我如何找到(迭代)有向图中从/到给定节点的所有循环?

例如,我想要这样的东西:

A->B->A
A->B->C->A

但不是: B->C->B

最佳答案

我在搜索中找到了这个页面,因为循环与强连通分量不同,我继续搜索,最后,我找到了一个有效的算法,它列出了有向图的所有(基本)循环。它来自 Donald B. Johnson,可以在以下链接中找到该论文:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

可以在以下位置找到 java 实现:

http://normalisiert.de/code/java/elementaryCycles.zip

可以找到约翰逊算法的

Mathematica 演示 here , 实现可以从右边( "Download author code" ) 下载。

注意:其实这个问题有很多算法。本文中列出了其中一些:

http://dx.doi.org/10.1137/0205007

根据文章,Johnson 的算法是最快的。

关于algorithm - 在有向图中查找所有循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/546655/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com