Tarjan 的算法错误地检测周期

Question

每当我运行任何图上的 tarjans 算法它总是声称有一个循环，例如这个图：

A -> B -> C

算法会告诉我有一个循环：

[a]
[b]

当有是一个循环时，例如：

A -> B -> C -> A

输出很奇怪：

[c, b, a]
[a]
[b]

这是我的实现：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.stream.Collectors;

public class Tarjans {

    private static class Node {
        public int index = -1, lowLink = -1;
        public String name;

        public Node(String name) {
            this.name = name;
        }

        public String toString() {
            return name;
        }
    }

    HashMap<String, Node> nodes = new HashMap<>();
    HashMap<String, ArrayList<Node>> graph = new HashMap<>();

    private int index = 0;
    private ArrayDeque<Node> visited = new ArrayDeque<>();
    private HashSet<String> stack = new HashSet<>();

    public ArrayList<ArrayList<Node>> tarjan() {
        ArrayList<ArrayList<Node>> cycles = new ArrayList<>();
        for (String key : graph.keySet()) {
            Node n = nodes.get(key);
            if (n == null) {
                System.err.println("what is " + n + "?");
                return new ArrayList<ArrayList<Node>>();
            }

            ArrayList<Node> cycle = strongConnect(n);
            if (cycle.size() > 0) {
                cycles.add(cycle);
            }
        }
        return cycles;
    }

    private ArrayList<Node> strongConnect(Node node) {
        node.index = index;
        node.lowLink = index;
        index += 1;

        visited.push(node);
        stack.add(node.name);

        ArrayList<Node> neighbours = graph.get(node.name);
        if (neighbours == null) return new ArrayList<>();

        neighbours.forEach(n -> {
            if (n.index == -1) {
                strongConnect(n);
                node.lowLink = Math.min(node.lowLink, n.lowLink);
            }
            else if (stack.contains(n.name)) {
                node.lowLink = Math.min(node.lowLink, n.index);
            }
        });

        ArrayList<Node> cycle = new ArrayList<>();
        if (node.lowLink == node.index) {
            Node p = null;
            do {
                p = visited.pop();
                stack.remove(p.name);
                cycle.add(p);
            } while (p != node);
        }
        return cycle;
    }

    private void foo() {
        nodes.put("a", new Node("a"));
        nodes.put("b", new Node("b"));
        nodes.put("c", new Node("c"));

        // A -> B -> C -> A
        graph.put("a", new ArrayList<>(Arrays.asList(nodes.get("b"))));
        graph.put("b", new ArrayList<>(Arrays.asList(nodes.get("c"))));
        graph.put("c", new ArrayList<>(Arrays.asList(nodes.get("a"))));

        ArrayList<ArrayList<Node>> cycles = tarjan();
        for (ArrayList<Node> cycle : cycles) {
            System.out.println("[" + cycle.stream().map(Node::toString).collect(Collectors.joining(",")) + "]");
        }
    }

    public static void main(String[] args) {
        new Tarjans().foo();
    }

}

但我不确定哪里出错了。我已经关注了关于 tarjans 算法的维基百科文章 1:1 和伪代码。我对图论和图算法非常陌生，所以我无法理解这里的错误是什么。

修复了 tarjan()

public ArrayList<ArrayList<Node>> tarjan() {
    ArrayList<ArrayList<Node>> cycles = new ArrayList<>();
    for (Node n : nodes.values()) {
        if (n == null) {
            System.err.println("what is " + n + "?");
            return new ArrayList<ArrayList<Node>>();
        }

        if (n.index == -1) {
            ArrayList<Node> cycle = strongConnect(n);
            if (cycle.size() > 0) {
                cycles.add(cycle);
            }   
        }
    }
    return cycles;
}

Answer 1

从问题中提出的代码的第一次修订来看，问题归结为 nearly 不够接近：I've followed the wikipedia article on [Tarjan's Strongly Connected Components] algorithm nearly 1:1 and the pseudocode.
（并且可能命名（要保存的变量）强连通分量 cycle：如果边 (a, b), (a, c), (b, a), (b , c) 和 (c, a) 属于一个图，vertices/nodes a, b, c 属于一个强连通分量，既不是循环也不是发生的循环（成对）共享顶点。）

已为已访问的节点调用 strongConnect() - 已在修订版 7 中修复。
从修订版 7 开始，只要节点没有 neighbours/successors，仍然会 not 检查节点是否符合 strongly connected component 的条件。 =30=] 一旦找到 强连接组件 就没有那么容易了：将 Set<Set<Node>> 作为数据成员 "of the algorithm(instance)" 添加到其中。

一旦你的实施开始工作并且代码得到清理和评论，我建议在 CODE REVIEW 上展示它：有很多的机会来改变每个人的生活（作为 (Java) 编码器）更容易，从你的开始。

Tarjan 的算法错误地检测周期

Tarjans algorithm wrongly detecting cycles

java

algorithm

graph

tarjans-algorithm

修复了 tarjan()