在有机图中找到循环

本文关键字：循环 | 更新日期: 2023-09-27 18:14:28

我想在一个有机构建的图中找到所有的循环。简而言之，当两个分支或路径在一个共同的顶点结束时，循环就发生了。就像
1 -> 2 -> 3 -> 4

5 -> 1 -> 4形成1->2->3->4->5->1的循环。

由于图的性质，我不能使用DFS或类似的算法，因为没有后边。我已经找到了在一个图中找到所有的循环基，用给定的顶点坐标和算法来识别无向图中的所有循环基以进入正确的方向，但是在两个线程中没有提出有效的算法。

在伪代码或实现形式中是否存在优化的解决方案，或者我应该倾向于任何提出的解决方案并自己优化它?在后一种情况下，我应该使用哪个提供的代码示例来达到这个目的?

期待您的回复。

在有机图中找到循环

我认为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

希望有所帮助

我得到了一个使用样本输入的DFS，但是每当我使用生成的图形作为输入时，它都无法找到任何循环。也许你可以在这方面帮助我，因为我似乎被困在一个逻辑黑洞里。

请注意输入数据的顺序如下:顶点顶点有零个或多个根顶点。

我正在查看以下伪代码:

nodes = dictionary(Vector2, Vertex)
vertices = GetData()
for each vertex in vertices
    bBackEdge = false
    //Check if vertex already exists
    //If true, we got a back-edge
    if nodes[vertex.Vector]
        tempVertex = nodes[vertex.Vector]
        bBackEdge = true
    else
        tempVertex = new Vertex(...)
        nodes.add(tempVertex.Vector, tempVertex )
    end of if
    for each root in tempVertex.Roots
        if nodes[root.Vector]
            tempRoot = nodes[root.Vector]
            tempRoot.Children.Add(vein)
            if bBackEdge
                vein.Children.Add(tempRoot)
            end of if
        end of if
    end of for
end of for
相关文章：