3

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

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

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

期待您的回复。

4

2 回答 2

0

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

希望能帮助到你

于 2013-05-20T12:14:41.893 回答
0

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

请注意，输入数据的顺序如下：vertex vert got zero or more root vertices。

我正在查看以下伪代码：

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
于 2013-05-21T15:58:49.297 回答