查找无向图中的所有循环

 shyaiqq 发布于 2023-02-10 13:59

我正在使用算法第4版来稍微改进我的图论.这些书附带了大量的图形处理代码.
目前,我遇到了以下问题:如何在无向图中找到所有周期?我想修改现有的循环检测代码来做到这一点.

这是重要的部分:

private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

现在,如果我要找到所有循环,我应该删除在找到循环时返回的行,并且每次创建一个循环时我都会存储它.我无法弄清楚的部分是:算法什么时候停止?我怎么能确定我找到了所有周期?

以上代码甚至可以通过某种方式修改,以便我找到所有循环?

撰写答案
今天,你开发时遇到什么问题呢?
立即提问
热门标签
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有