深度优先搜索算法python
时间: 2023-09-16 08:13:06 浏览: 65
深度优先搜索算法(DFS)是一种图搜索算法,用于从起点开始沿着一条路径不断向下搜索直到不能再继续为止,然后再折返,开始搜索下一条候补路径。在Python中,可以通过递归的方式实现深度优先搜索算法。
以下是一个使用深度优先搜索算法求解二叉树最大深度的示例代码:
```
# 定义二叉树的节点类
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 深度优先搜索函数
def maxDepth(root):
if root is None:
return 0
else:
left_height = maxDepth(root.left) # 递归搜索左子树的最大深度
right_height = maxDepth(root.right) # 递归搜索右子树的最大深度
return max(left_height, right_height) + 1 # 返回左右子树中最大深度加1
# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
solution = Solution()
result = solution.maxDepth(root) # 调用深度优先搜索函数求解二叉树的最大深度
print("二叉树的最大深度为:", result)
```
在上述代码中,我们首先定义了一个二叉树的节点类`TreeNode`,然后实现了一个深度优先搜索函数`maxDepth`,该函数通过递归方式计算二叉树的最大深度。最后,我们创建了一个二叉树的示例,并调用深度优先搜索函数求解二叉树的最大深度。运行代码,即可得到二叉树的最大深度。
请注意,上述代码仅为示例,实际应用中可能需要根据具体问题进行适当的修改和调整。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [深度优先搜索python](https://blog.csdn.net/weixin_49321128/article/details/124934904)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [算法第六期——DFS初入门(深度优先搜索)(Python)](https://blog.csdn.net/m0_69478345/article/details/128476009)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]