java实现dfs和bfs算法

### Java中DFS和BFS算法的实现 #### 深度优先搜索 (DFS) 深度优先搜索是一种通过递归或显式使用栈的方式遍历图或树的算法。以下是基于递归方式实现的DFS代码： ```java public class TreeNode { int val; TreeNode left, right; public TreeNode(int item) { this.val = item; this.left = this.right = null; } } public class DFSExample { public void DFS(TreeNode node) { if (node == null) return; System.out.print(node.val + " "); // 访问当前节点 DFS(node.left); // 遍历左子树 DFS(node.right); // 遍历右子树 } } ``` 上述代码展示了如何利用递归来完成对一棵二叉树的深度优先遍历[^2]。 如果希望不采用递归而改用显式的栈，则可以这样写： ```java import java.util.Stack; public class IterativeDFS { public void iterativeDFS(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); if(root != null){ stack.push(root); while(!stack.isEmpty()){ TreeNode current = stack.pop(); System.out.print(current.val + " "); if(current.right != null){ stack.push(current.right); } if(current.left != null){ stack.push(current.left); } } } } } ``` 这段代码实现了非递归版本的DFS，它借助`Stack`类来模拟函数调用堆栈的行为[^3]。 #### 广度优先搜索 (BFS) 对于广度优先搜索来说，最常用的辅助数据结构是队列(queue)，因为我们需要按层处理每一个结点及其相邻结点。下面给出了一种典型的BFS实现方法： ```java import java.util.LinkedList; import java.util.Queue; public class BFSExample { public void BFS(TreeNode root){ Queue<TreeNode> queue = new LinkedList<>(); if(root != null){ queue.add(root); while(!queue.isEmpty()){ TreeNode current = queue.poll(); // 取出并移除头部元素 System.out.print(current.val + " "); if(current.left != null){ queue.add(current.left); } if(current.right != null){ queue.add(current.right); } } } } } ``` 此程序片段定义了一个名为`BFS()`的方法，用于执行给定二叉树上的广度优先搜索操作[^4]。 --- ### 总结 无论是DFS还是BFS，它们都是用来解决特定问题的强大工具。选择哪种取决于具体应用场景以及个人偏好等因素。以上提供了两种基本形式——递归版与迭代版DFS还有标准BFS实现供参考学习之用。