Tarjan强连通分量算法

Question

有人能告诉我怎样才能让这个“更好”吗？如果你能看到任何明显的细节，我可以改变，以加快速度，这将是伟大的--尽管这不是优先事项。

public class Tarjans {

    private static class Node {
        // -1, -1, our node is unvisited
        // by default.
        public int index = -1, lowLink = -1;
        public String name;

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

        public String toString() {
            return name;
        }
    }

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

    private int index = 0;

    // for a DFS, basically
    private ArrayDeque<Node> visited = new ArrayDeque<>();
    private HashSet<String> stack = new HashSet<>();

    // stores our strongly connected componts
    // from the algorithm pass
    private HashSet<HashSet<Node>> scc = new HashSet<>();

    public HashSet<HashSet<Node>> tarjan() {
        for (Node n : nodes.values()) {
            if (n != null && n.index == -1) {
                strongConnect(n);
            }
        }
        return scc;
    }

    private void 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) {
            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);
                }
            });
        }

        if (node.lowLink == node.index) {
            HashSet<Node> cycle = new HashSet<>();
            while (true) {
                Node p = visited.pop();
                stack.remove(p.name);
                cycle.add(p);

                if (p == node) {
                    break;
                }
            }
            if (cycle.size() > 1) {
                scc.add(cycle);         
            }
        }
    }

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

        graph.put("bs", new ArrayList<>(Arrays.asList(nodes.get("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"))));

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

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

}

Answer 1

没有理由在graph中使用字符串作为键。默认情况下，基于对象的唯一性，可以将对象用作hashmap中的键。

没有理由认为值必须是ArrayLists，而只是使用List。

HashMap<Node, List<Node>> graph = new HashMap<>();

这可以清理init代码，因为您不必执行new ArrayList<>，而可以直接传递Arrays.asList(nodes.get("a"))。

尽管如此，您可以将邻居的列表直接放到Node中，而不必在strongConnect中查找。