算法概述
深度优先搜索（Depth-First Search，DFS）是十分常见的图搜索方法之一。深度优先搜索会沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。深度优先遍历按照深度优先搜索的方式对图进行遍历。并且每个节点只能访问一次。
深搜优先搜索的本质上就是持续搜索，遍历了所有可能的情况，必然能得到解。DFS搜索的流程是一个树的形式，每次一条路走到黑。
深搜优先搜索最早是使用在开发爬虫早期使用较多的方法。它的目的主要是达到被搜索结构的叶结点：即那些不包含任何超链的HTML文件)。沿着HTML目录层级下探，直到最后一层，然后回退到上层，被访问过的节点会被标记，然后查看是否有其他节点，如果有则继续下突然，直到最后一层。一次类推直到所有节点都被查找。
深度优先搜索算法思想
深度优先遍历的秘籍：后访问的节点，其邻接点先被访问。根据深度优先遍历的秘籍，后来的先服务，这可以借助“栈”来实现。递归本身就是使用“栈”实现的，因此使用递归的方法更方便。
深度优先遍历图的方法是，从图中某顶点v出发：
- 访问顶点v；
- 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
- 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
深度优先搜索算法步骤
- 初始化图中的所有节点均未被访问；
- 从图中的某个节点v出发，访问v并标记其已经被访问；
- 依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复步骤2和步骤3）
算法实现
图的DFS遍历
def dfs(graph,start,visited):
# 访问当前节点
pirnt(start,end='')
# 标记当前节点为已访问
visited[start]=True
# 遍历当前节点的邻居节点
for neighbor in graph[start]:
# 如果邻居节点未被访问，则继续深度优先搜索
if not visited[neighbor]:
dfs(graph,neighbor,visited)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['B'],
'F': ['C'],
'G': ['C']
}
# 标记节点是否已访问的列表
visited = {node: False for node in graph}
# 从节点A开始进行DFS遍历
print("DFS遍历结果：")
dfs(graph, 'A', visited)二叉树的DFS遍历
# 二叉树节点定义
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 二叉树的DFS遍历
def dfs_binary_tree(root):
if root is None:
return
print(root.val, end=' ')
dfs_binary_tree(root.left)
dfs_binary_tree(root.right)
# 构造二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 二叉树的DFS遍历
print("二叉树的DFS遍历结果：")
dfs_binary_tree(root)Leecode.2062 统计字符串中的元音子字符串
题目链接：https://leetcode.cn/problems/count-vowel-substrings-of-a-string/description/
子字符串 是字符串中的一个连续（非空）的字符序列。
元音子字符串 是 仅 由元音（'a'、'e'、'i'、'o' 和 'u'）组成的一个子字符串，且必须包含 全部五种 元音。
给你一个字符串 word ，统计并返回 word 中 元音子字符串的数目 。
class Solution:
def countVowelSubstrings(self, word: str) -> int:
cnt=0
for i in range(len(word)-4):
for j in range(i,len(word)+1):
if set(word[i:j])==set('aeiou'):
cnt+=1
return cnt
Comments NOTHING