4

给定一个图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;
}

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

4

2 回答 2

4

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

我认为您应该将问题分为两部分：

1.查找图中的所有循环（将它们保存在哈希表或类似列表中）

2.找出哪些循环包含某个节点。

1 的解决方案：第一步有很多在线算法，比如这个可以进行细微调整的算法，或者这个计算周期数的算法，您可以更改它以保存它找到的周期。

解决方案 2：这取决于您如何保存周期，但它是一种简单的搜索算法。

请注意，如果您只想一次找到一个节点的答案，则此解决方案不是最佳的，但如果您希望能够找到任何给定节点和任何给定时间的周期数，它确实很好。

于 2018-12-03T12:44:14.073 回答
0

我最终添加了一个额外Map<Node, Stack<Edge>>的previousEdges, 来跟踪在回溯中要遍历的边。然后该unwindStack函数遍历这个链表，递增Edge.cycles直到它到达Node结束循环的 （loopNode）：

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

    onStack.put(currentNode, Boolean.TRUE);

    for (Edge outEdge : currentNode.getEdges()) {
        Node nextNode = outEdge.getEnd();
        if (component.contains(nextNode)) {

            // put the edge on the previousEdges stack
            if (!previousEdges.containsKey(nextNode)) {
                previousEdges.put(nextNode, new Stack<>());
            }
            previousEdges.get(nextNode).push(outEdge);

            if (onStack.getOrDefault(nextNode, false)) {
                // found loop
                unwindStack(nextNode, nextNode);
                // pop the previousEdge off the stack, so that we undo any
                // overwriting of history for another branch.
                previousEdges.get(nextNode).pop();

            }
            else {
                // recursively call this function
                labelEdges(nextNode, component);
            }
        }
    }
    onStack.put(currentNode, Boolean.FALSE);
}

private void unwindStack(Node currentNode, Node loopNode) {
    Edge previousEdge;
    try {
        previousEdge = previousEdges.get(currentNode).peek();
    } catch (EmptyStackException e) {
        previousEdge = null;
    }
    if (previousEdge != null) {
        // increment edgeCycles entry by 1
        edgeCycles.merge(previousEdge, 1, Integer::sum);
        Node previousNode = previousEdge.getStart();
        if (previousNode != loopNode) {
            unwindStack(previousNode, loopNode);
        }
    }
}
于 2018-12-04T12:16:25.133 回答