深度优先搜索实现：从树遍历到网络结构探索

在处理复杂数据结构时，比如文件系统目录、网页DOM结构，甚至内网中层层嵌套的设备连接关系，经常需要一种能“钻到底再回头”的遍历方式。深度优先搜索（DFS）就是干这个活的常用方法。它不追求广撒网，而是选定一个方向就一路深入，直到走不通才回退，换条路继续。

核心思路：先到底，再回溯

想象你在公司内网排查一台无法访问的设备。这台设备可能通过多层交换机、路由器连接。你从主控服务器出发，不是把每一级的所有接口都检查一遍，而是挑一个端口顺着查下去，查到尽头发现不对，再退回上一级换另一个端口。这就是DFS的思维——一条路走到黑，不行就回退一步。

用递归实现最直观

在编程中，递归天然适合表达这种“深入-返回”的逻辑。以下是一个基于二叉树的DFS中序遍历实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public void dfs(TreeNode node) {
    if (node == null) return;
    
    dfs(node.left);   // 先深入左子树
    System.out.print(node.val + " "); // 访问当前节点
    dfs(node.right);  // 再深入右子树
}

这段代码会按照“左-根-右”的顺序打印节点值。每次调用自身时，程序的执行上下文被压入调用栈，回退时自然弹出，实现了自动回溯。

非递归版本：手动维护栈

有些场景下递归可能引发栈溢出，比如树非常深。这时可以用显式的栈结构来模拟递归过程：

import java.util.Stack;

public void dfsIterative(TreeNode root) {
    if (root == null) return;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        
        // 先压右子节点，再压左子节点
        // 这样左子节点会先被弹出处理
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

这种方式更灵活，也更容易控制遍历流程。比如在网络拓扑扫描中，你可以随时暂停、记录状态，甚至动态调整搜索路径。

在内网设备探测中的应用

假设你有一张内网设备连接图，用邻接表表示。你想从网关出发，找出所有可达设备。DFS可以轻松完成：

import java.util.*;

public class NetworkScanner {
    private Map<String, List<String>> network = new HashMap<>();
    private Set<String> visited = new HashSet<>();
    
    public void scan(String ip) {
        if (visited.contains(ip)) return;
        
        System.out.println("访问设备: " + ip);
        visited.add(ip);
        
        for (String next : network.getOrDefault(ip, Collections.emptyList())) {
            scan(next);
        }
    }
}

只要network数据准备好了，scan方法就能像探针一样深入整个内网结构，把每一台连通的设备都标记出来。这种能力在做安全审计或故障排查时特别实用。