java - 用它参与的循环数标记边

Question

给定一个图 G = (V, E)，使用 DFS，我如何用它参与的简单循环数来标记每条边？当我从图中提取强连通分量时，我已经用后序标记了节点，所以也许我可以以某种方式使用该信息。

private Integer labelEdges(Node currentNode, Set<Node> component) {

    Integer numLoops = 0;
    currentNode.onStack = true;

    for (Edge outEdge : currentNode.getEdges()) {
        Node nextNode = outEdge.getEnd();
        if (component.contains(nextNode)) {
            if (nextNode.onStack) {
                // loop
                numLoops += 1;
            }
            else {
                numLoops += labelEdges(nextNode, component);
            }
            outEdge.cycles = numLoops;
        }

    }
    currentNode.onStack = false;

    return numLoops;
}

我似乎无法清楚地推理这一点。谁能指出我正确的方向？

Answer 1

如果没有看到您的完整代码，很难给您一个完整的答案，但我认为这会有所帮助。请注意，提供的链接适用于无向图。

我认为你应该把问题分成两部分:

1.找出图中的所有循环(将它们保存在哈希表或类似表中)

2. 找出那些循环中的哪些包含特定节点。

解决方案1:第一步网上有很多算法，比如this one这将与微小的调整或this one一起工作计算循环次数，您可以更改它以保存它找到的循环。

解决方案 2: 这取决于您如何保存循环，但这是一个简单的搜索算法。

请注意，如果您只想一次找到一个节点的答案，则此解决方案不是最佳解决方案，但如果您希望能够找到任何给定节点和任何给定时间的循环数，则该解决方案非常好。