c# - 在有机图中查找循环

Question

我想在有机构建的图中找到所有循环。简而言之，当两个分支或路径终止于一个公共(public)顶点时，就会发生循环。有点像
1->2->3->4
1->5->4
形成1->2->3->4->5->1的循环。

由于图形的性质，我不能使用 DFS 或类似算法，因为没有后边。我找到了 Find All Cycle Bases In a Graph, With the Vertex Coordinates Given和 Algorithms to Identify All the Cycle Bases in a UnDirected Graph进入正确的方向，但在两个线程中没有提出有效的算法。

是否有伪代码或实现形式的优化解决方案，或者我应该倾向于任何提供的解决方案并自己优化它？在后一种情况下，我应该为此目的使用哪个提供的代码示例？

期待您的回复。

Answer 1

我认为 DFS 是否适合您。

探索图直到遇到已经探索过的顶点

这是伪代码:

function DFSFindCycle(Start, Goal)
push(Stack,Start)
while Stack is not empty
    var Node := Pop(Stack)
    Color(Node, Grey)
    for Child in ExpandNotExploredEdges(Node)
        if Node.color != White
    return true 
        if Node.color = White
           push(Stack, Child)
           label edge e, Node:Child as explored
    Color(Node, Black)
retrun false

希望对你有帮助