赞
踩
目录
深度优先搜索通常用递归或栈(Stack)来实现。算法的核心思想是通过递归或栈,在每一层选择一个未访问过的相邻节点,探索到最深的层次,直到满足结束条件。
在了解了深度优先搜索的概念之后,我们来看一下实现深度优先搜索的基本步骤:
1. 选择起始节点: 选择一个节点作为深度优先搜索的起点。
2. 访问节点:将当前节点标记为已访问,并执行相应的操作。
3. 递归或压栈: 从当前节点的邻接节点中选择一个未访问过的节点,进行递归调用或将其压入栈中。
4. 回溯:当前节点没有未访问过的邻接节点时,进行回溯,即返回到上一层的节点,选择其他路径。
5. 结束条件: 当所有节点都被访问过或达到特定条件时,结束搜索。
- // 定义树节点的类
- class TreeNode {
- int val; // 节点的值
- TreeNode left, right; // 左子节点和右子节点
-
- // 构造方法,用于初始化节点
- public TreeNode(int val) {
- this.val = val; // 初始化节点的值
- this.left = this.right = null; // 初始时左右子节点为空
- }
- }
-
- public class Main {
- public static void main(String[] args) {
- // 构建一个二叉树
- TreeNode root = new TreeNode(1);
- root.left = new TreeNode(2);
- root.right = new TreeNode(3);
- root.left.left = new TreeNode(4);
- root.left.right = new TreeNode(5);
-
- // 深度优先搜索
- dfs(root);
- }
-
- // 深度优先搜索的实现
- public static void dfs(TreeNode node) {
- // 如果当前节点为空,直接返回
- if (node == null) {
- return;
- }
-
- // 访问当前节点
- System.out.print(node.val + " ");
-
- // 递归访问左子树
- dfs(node.left);
-
- // 递归访问右子树
- dfs(node.right);
- }
- }
代码运行结果:
以文中代码为例子,可以画出二叉树的结构,并在访问每个节点时标记出来。
深度优先搜索(DFS)是一种遍历树的方法,它从当前节点开始,先访问它,然后依次递归地访问它的左子树和右子树。以文中的代码为例,深度优先搜索的遍历顺序如下:
1. 访问根节点 1。
2. 递归地访问左子树,即节点 2。
3. 在节点 2 的基础上,递归地访问左子树,即节点 4。
4. 在节点 2 的基础上,递归地访问右子树,即节点 5。
5. 回溯到节点 2,再递归地访问右子树,即节点 3。
深度优先搜索有三种主要的实现方式:
1. 先序遍历: 先访问根节点,然后递归访问左子树和右子树。
2. 中序遍历: 先递归访问左子树,然后访问根节点,最后递归访问右子树。
3. 后序遍历:先递归访问左子树和右子树,最后访问根节点。
文中的代码,采用的是先序遍历,即先访问根节点,然后递归访问左子树和右子树。
以下为代码的深度优先搜索可视化过程:
源码链接:
链接:百度网盘 请输入提取码
提取码:LLL
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。