图表示的树全向下路径查找及DFS代码问题排查

现有代码的核心问题 #

• 全局visited标记逻辑错误：你的需求是输出所有向下的可行路径，不是对图做一次去重遍历。节点被首次访问后就标记为已访问，后续以其他节点为起点的路径要访问该节点时会被直接拦截，比如首次从根节点1走到5后，5被标记为已访问，后续以3为起点遍历到5的时候就会跳过，自然生成不了3->5->6这类路径。而且你的场景是无环的向下树结构，根本不需要visited去重。
• 路径处理逻辑仅支持两级路径：你每次处理当前节点时，只会将当前节点拼入path，遍历邻居时仅拼接一级邻居就打印，随后马上回退path的最后一位，处理完当前节点的所有邻居后直接把path置空。这种逻辑下永远不会保留更长的路径前缀，比如你走到节点5的时候，根本不会带着3->5的前缀继续处理子节点6，自然生成不了长度大于2的路径。
• 仅触发了根节点的路径查找：你只调用了一次dfs(1)，要输出所有节点作为起点的路径，需要将每个节点都作为源点单独触发一次路径查找。

修复方案 #

核心思路是：每次路径查找时，将当前路径和节点绑定传递，每走一步就打印新生成的路径，不需要全局visited标记。
以下是简洁的递归实现示例：

// 预处理邻接表，示例结构为：1→[2,3]、3→[4,5]、5→[6]，其余节点无邻接子节点
static Map<Integer, List<Integer>> adjList = new HashMap<>();

public static void main(String[] args) {
    // 初始化边
    adjList.put(1, Arrays.asList(2,3));
    adjList.put(3, Arrays.asList(4,5));
    adjList.put(5, Arrays.asList(6));
    // 所有节点都作为起点触发一次路径查找
    Set<Integer> allNodes = new HashSet<>(Arrays.asList(1,2,3,4,5,6));
    for (int source : allNodes) {
        dfs(source, String.valueOf(source));
    }
}

static void dfs(int currentNode, String currentPath) {
    // 当前节点无子节点，直接返回
    if (!adjList.containsKey(currentNode)) {
        return;
    }
    // 遍历所有向下的邻接节点
    for (int neighbor : adjList.get(currentNode)) {
        String newPath = currentPath + "->" + neighbor;
        // 每生成一条新路径就打印
        System.out.println(newPath);
        // 带着新路径继续向下遍历
        dfs(neighbor, newPath);
    }
}

如果要保留迭代实现，只需要把栈的存储内容从单个节点改成「节点+当前路径」的组合即可：

static void dfs(int source) {
    // 栈中存储（当前节点，当前到该节点的路径）
    Stack<Pair<Integer, String>> stack = new Stack<>();
    stack.push(new Pair<>(source, String.valueOf(source)));
    
    while (!stack.isEmpty()) {
        Pair<Integer, String> curr = stack.pop();
        int currNode = curr.getKey();
        String currPath = curr.getValue();
        
        if (!adjList.containsKey(currNode)) {
            continue;
        }
        // 倒序遍历保证输出顺序和递归一致，不需要可省略
        List<Integer> neighbors = adjList.get(currNode);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            int neighbor = neighbors.get(i);
            String newPath = currPath + "->" + neighbor;
            System.out.println(newPath);
            stack.push(new Pair<>(neighbor, newPath));
        }
    }
}

运行后输出完全符合预期要求。

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