基于AdjacencyGraph实现DepthFirstTraversal的traverse方法测试不通过问题

原代码存在的核心问题 #

• 迭代器逻辑错误导致节点漏遍历：traverse()方法中判断是否调用visit()的条件写为if (nodeIterator.hasNext())，该条件仅判断当前节点之后是否还有其他节点，会导致图的最后一个节点永远不会被处理，无法覆盖所有连通分量。
• 访问标记逻辑完全颠倒：初始化visited时所有节点值为false（代表未访问），但在遍历邻居时的判断条件为if (visited(nextNode.next()))，即仅当节点已被标记为已访问时才触发递归遍历，完全违背DFS的递归触发逻辑。
• Map操作错误引发空指针/标记失效：visit()方法中错误写为visited.remove(node, true)，本意是标记节点为已访问，实际是删除Map中对应节点的记录，后续查询visited.get(node)时会返回null，触发空指针异常。
• 迭代器重复调用next()引发元素跳过/异常：遍历邻居的循环中，同一次循环内连续两次调用nextNode.next()，第一次用于判断访问状态，第二次作为递归参数，会直接跳过中间元素，且迭代到最后会触发NoSuchElementException。
• 成员变量状态残留问题：visited和traversalList作为类成员变量，未在每次traverse()调用时重置，多次执行遍历会残留上一次的遍历结果和访问标记，导致结果错误。

修正后的正确实现代码 #

public class DepthFirstTraversal<T> extends AdjacencyGraph<T> implements Traversal<T> {

    @Override
    public List<T> traverse() throws GraphError {
        // 按业务要求校验图合法性：无节点或无边时抛出异常
        if (getNoOfNodes() == 0 || getNoOfEdges() == 0) {
            throw new GraphError();
        }
        // 每次遍历前在方法内初始化状态，避免跨调用残留
        HashMap<T, Boolean> visited = new HashMap<>();
        List<T> traversalList = new ArrayList<>();
        Set<T> nodes = getNodes();

        // 初始化所有节点为未访问状态
        for (T node : nodes) {
            visited.put(node, false);
        }

        // 遍历所有节点，兼容非连通图的每个独立连通分量
        for (T node : nodes) {
            // 仅对未访问的节点启动DFS
            if (!isNodeVisited(node, visited)) {
                dfsRecursiveVisit(node, visited, traversalList);
            }
        }
        return traversalList;
    }

    // 递归执行DFS访问
    private void dfsRecursiveVisit(T node, HashMap<T, Boolean> visited, List<T> traversalList) throws GraphError {
        // 记录当前节点到遍历结果，同时标记为已访问
        traversalList.add(node);
        visited.put(node, true);

        Set<T> neighbours = getNeighbours(node);
        // 遍历当前节点的所有邻居
        for (T neighbour : neighbours) {
            // 仅对未访问的邻居递归深入
            if (!isNodeVisited(neighbour, visited)) {
                dfsRecursiveVisit(neighbour, visited, traversalList);
            }
        }
    }

    // 统一处理节点访问状态查询，避免空指针
    private boolean isNodeVisited(T node, HashMap<T, Boolean> visited) {
        return visited.getOrDefault(node, false);
    }
}

关键修正点说明 #

• 取消原本作为类成员的visited、traversalList变量，改为在traverse()方法内局部创建，彻底避免多次调用遍历方法时的状态残留问题。
• 替换原来易出错的显式迭代器写法为增强for循环，从根源消除重复调用next()导致的元素跳过、越界异常问题。
• 修正原代码的逻辑错误：将删除Map节点的错误操作替换为写入true标记已访问状态，把递归触发条件调整为仅未访问的节点才需要递归深入，完全匹配DFS算法的核心逻辑。
• 增加getOrDefault做访问状态查询，兼容Map缺失节点的边界场景，避免空指针异常。
• 调整连通分量的处理逻辑为遍历所有节点，只要节点未被访问就启动DFS，确保非连通图的所有节点都能被遍历到。

内容的提问来源于stack exchange，提问作者Ollie