查找周期深度优先搜索 [英] Finding cycles Depth-first-search

问题描述

我正在尝试通过删除一条边来修复图形。我遇到的唯一问题是，例如在图形中有多个循环时：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.

这篇关于查找周期深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！