algorithm - 在有向图中找到返回到起始节点的所有循环，直到一定长度

Question

我想在有向图中查找（并跟踪路径）长度为 N 的所有循环，这些循环开始并返回到我指定的给定“开始”节点。

我试过 bellman ford，因为事实证明我也对负重量循环感兴趣，但 bellman 只返回这样一个循环的存在，并且使用 parent[] 我可以导航到至少检测一个循环，但不是'全部'他们。

接下来，我尝试从起始节点执行 DFS，并捕获任何有边缘返回原点且长度小于 N 的路径。但这似乎不太奏效。

有没有一个标准的算法呢？感谢任何指针。谢谢你！

更新：如果我稍微调整一下 DFS 逻辑，我可以得到似乎是 DFS 的正确答案。如果我将其设置为 false 以取消将节点标记为已访问，它似乎会为我生成所有循环，如果不是（标准 DFS）我不会得到像 A=>B=>C=>A 和 A=>C= 这样的循环>A. 这仍然是正确的 DFS 吗？这是从给定起始节点获取所有循环的正确方法吗？

// Recursive depth first search graph traveller
protected dfsWorker(curNode: string, dfsState : DFSState) {
    if (dfsState.finished) {
        return;
    }
    if (!dfsState.traveller.onDfsProcessNodeEarly(curNode, dfsState)) {
        return;
    }
    dfsState.visited.set(curNode, true);
    dfsState.time = dfsState.time + 1 
    dfsState.entryTimes.set(curNode, dfsState.time);

    // Visit all neighbours
    let neighbors = this.graph.get(curNode);
    if (neighbors) {
        for (let [neighbor, graph_edge_node] of neighbors) {

            if (!dfsState.visited.get(neighbor)) {
                // Newly visited node

                dfsState.parent.set(neighbor, curNode);

                dfsState.traveller.onDfsProcessEdgePreRecurse(curNode, neighbor, true, dfsState);

                // Recurse
                this.dfsWorker(neighbor, dfsState);

                dfsState.traveller.onDfsProcessEdgePostRecurse(curNode, neighbor, true, dfsState);
            }
            else
            {
                dfsState.traveller.onDfsProcessEdgePreRecurse(curNode, neighbor, false, dfsState);
            }

            if (dfsState.finished) {
                return;
            }
        }
    }

    dfsState.traveller.onDfsProcessNodeLate(curNode, dfsState);
    dfsState.time = dfsState.time + 1;
    dfsState.exitTimes.set(curNode, dfsState.time);
    dfsState.processed.set(curNode, true);

    // hack test -- 

    dfsState.visited.set(curNode, false);
}

标签： algorithmdirected-acyclic-graphs