每当我在任何图上运行 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();
}
}
但我不确定我哪里出错了。我已经按照近 1:1 的比例关注了关于 tarjans 算法的维基百科文章和伪代码。我对图论和图算法很陌生，所以我无法理解这里的错误是什么。
修复 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;
}