查找周期深度优先搜索

本文介绍了查找周期深度优先搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试通过删除一条边来修复图形。我遇到的唯一问题是，例如在图形中有多个循环时：0 3，2 3，0 2，1 2，31。这可以通过提取3 1来解决，但是我如何让该程序没有3 1是必须去除的边缘吗？

I am trying to repair graphs by deleting one edges. The only problem I am running in to is, when there are multiple cycles in the graph for example: 0 3, 2 3, 0 2, 1 2, 3 1. This can be fixed by extracting 3 1, but how do I let the program no that 3 1 is the edge that has to be removed?

有什么建议吗？ ：）

注释中的格式化代码...

... else if (backedges.Count > 1) { foreach (Side side in backedges) { Node end = Side.node2; Node begin = Side.node1; List<Side> allsidesycle = new List<Side>(); while (begin != Side.node2) { end = begin; begin = begin.pi; Side be = new Side(begin, end); allsidescycle.Add(be); }

推荐答案

查找您可能想要的循环使用广度优先搜索（bfs）。 在未加权（或相等加权）图的受让人上使用bfs，则首次访问节点是到达该节点的最短路径。 如果您第二次访问它-您有一个循环。要删除它，可以通过删除第二条边来修改图形。

To find cycles you may want to use breadth first search (bfs). Using bfs on unweighted (or equally weighted) graph grantees that then the first time a node is visited is the shortest path to that node. If you visit it for the second time - you have a cycle. To remove it modify the graph by deleting that 2nd edge.