java - 测试图中两个节点之间是否存在路径

Question

我知道已经有类似的问题，但我希望评估我的搜索方法。我使用了DFS算法来找出两个节点之间是否有路由。这是我的代码，我想知道是否存在一个测试用例，其中我的代码会因结果而失败。

public boolean routeExists(Node start, Node end) {
    Set<Node> visited = new HashSet<>();
    Stack<Node> stack = new Stack<>();

    visited.add(start);
    stack.push(start);

    while(!stack.isEmpty()) {
        Node current = stack.pop();

        if(current.getValue() == end.getValue()) {
            return true;
        }

        for(Node adj : current.getAdjacent()) {
            // keep track of visited nodes
            if(!visited.contains(adj)) {
                stack.push(adj);
                visited.add(adj);
            }
        }
    }

    return false;
}

我已经进行了编辑，现在代码会跟踪访问过的节点，如果过去访问过它们，则不会扩展它们。我相信现在应该可以了。

Answer 1

对于许多输入图，此代码将进入无限循环。

考虑在边缘为以下情况时查找从 A 到 B 的路线:

A->B
A->C
C->A

您的代码将首先将 B 压入列表，然后压入 C，然后访问 C 并将 A 压入列表，然后重复，直到发生堆栈溢出。

如果与 wikipedia 进行比较

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

您会发现您错过了检查是否尚未发现新顶点的测试。