深度优先算法
原创
一、介绍
在这段时间中，我一直在看算法问题，在进行刷题；前面还提到了贪心算法，解释了什么是贪心算法，并使用其算法解决了一些算法问题。
但本文，会解释什么是深度优先算法，与其相对应的是广度优先算法。
我们先来看看什么是深度优先，再扩展到广度优先。
同样的，还是先看看百度词条的解释，是什么深度优先
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
最开始的介绍，很模糊。不过在后面的介绍中，解释了它为图算法中的一种，及点线点相类似的算法题解法。
点线点问题，我们便可以考虑使用深度优先，或者广度优先去解决。
二、深度优先
现在我们看这么一道题目，出自力扣的94题，链接如下
image-20250126100410898
对二叉树这个数据结构非常了解是吧，对于中序遍历，想必大家也是信手拈来
但我这边还是说明一下，所谓中序遍历，就是将二叉树这样排列进行输出，leftNode、middleNode、rightNode
但本章节需要使用到深度优先算法去解题，那么我们该如何进行编码呢，大家可以去力扣试试
package com.banmoon.arithmetic.leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=problem-list-v2&envId=depth-first-search">二叉树的中序遍历</a>
*/
public class Question94 {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root != null) {
// 如果左子节点有值，就优先递归左边的，一直到最深处，再返回
if (root.left != null) {
result.addAll(inorderTraversal(root.left));
}
result.add(root.val);
if (root.right != null) {
result.addAll(inorderTraversal(root.right));
}
}
return result;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}就像我上面注释说的，如果左子节点有值，就优先递归左边的，一直到最深处，再返回
这就是深度优先算法的核心所在，及在图解问题中，将一个方向的探索进行到最深处，直到有结果后返回
这个结果有时候不是正向的，也可能代表负向的结果；带上这个结果返回到最近一次的递归分叉点，然后尝试走向另一个方向
直到尝试完所有的可能，根据不同的图解问题，答案也是不同的
比如说，迷宫问题，如果采用深度优先，极可能中途就可以返回正确的路径了，而不用深度遍历所有的可能性
三、单词搜索
我们再来看一道算法题，力扣链接如下
image-20250126103234459
下面看一下解题思路，这个二维数组，其中每一个char我们都可以当做一个节点，节点与节点之间的连接最多有4个方向
即上、下、左、右；
- 所以我们可以遍历数组中的每一个元素，对其上下左右的元素进行判断，
- 如果符合目标单词的字母，则继续上下左右的进行判断；
- 一旦有一个方向不符合单词的字母，我们就返回到上一个节点元素，寻找另一个方向进行深入判断
代码如下
package com.banmoon.arithmetic.leetcode;
/**
* <a href="https://leetcode.cn/problems/word-search/?envType=problem-list-v2&envId=depth-first-search">单词搜索</a>
*/
public class Question79 {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
boolean[][] wordPath = new boolean[board.length][board[i].length];
boolean result = exist(board, i, j, word, 0, wordPath);
if (result) {
return true;
}
}
}
return false;
}
public boolean exist(char[][] board, int i, int j, String word, int currentIndex, boolean[][] wordPath) {
// 判断自身
wordPath[i][j] = true;
boolean result = board[i][j] == word.charAt(currentIndex);
if (!result) {
return false;
}
if (currentIndex == word.length() - 1) {
return true;
}
currentIndex++;
// 上
if (i > 0 && !wordPath[i - 1][j]) {
result = exist(board, i - 1, j, word, currentIndex, wordPath);
if (result) {
return true;
} else {
wordPath[i - 1][j] = false;
}
}
// 下
if (i < board.length - 1 && !wordPath[i + 1][j]) {
result = exist(board, i + 1, j, word, currentIndex, wordPath);
if (result) {
return true;
} else {
wordPath[i + 1][j] = false;
}
}
// 左
if (j > 0 && !wordPath[i][j -1]) {
result = exist(board, i, j - 1, word, currentIndex, wordPath);
if (result) {
return true;
} else {
wordPath[i][j - 1] = false;
}
}
// 右
if (j < board[i].length - 1 && !wordPath[i][j + 1]) {
result = exist(board, i, j + 1, word, currentIndex, wordPath);
if (result) {
return true;
} else {
wordPath[i][j + 1] = false;
}
}
return false;
}
}力扣运行结果如下
image-20250126123847854
四、最后
除去深度优先，还有广度优先，这两个算法成对出现，像某些不适合使用深度优先算法的场景，往往可以使用广度优先算法进行解决
那么，本文先提供深度优先算法的核心，希望大家能够理解
在点线点问题中，这两种算法是需要优先考虑的；
不过，在实际的工作中，往往没有这个深度广度算法的意识，但在遍历的过程中，我们会用到深度或广度的思想。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
