递归实现的深度优先搜索方法
时间: 2023-12-07 17:39:02 浏览: 39
以下是Python中递归实现的深度优先搜索方法的示例代码:
```python
# 定义一个二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 定义深度优先搜索函数
def dfs(node):
if not node:
return
print(node.val)
dfs(node.left)
dfs(node.right)
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 调用深度优先搜索函数
dfs(root)
```
在上述代码中,我们首先定义了一个二叉树节点类,然后定义了深度优先搜索函数`dfs`。在`dfs`函数中,我们首先判断当前节点是否为空,如果为空则直接返回;否则,我们先输出当前节点的值,然后递归调用左子树和右子树的`dfs`函数。
最后,我们创建了一个二叉树,并调用`dfs`函数进行深度优先搜索。
相关问题
用栈实现深度优先搜索和用递归实现深度优先搜索的区别
以下是用栈实现深度优先搜索和用递归实现深度优先搜索的区别:
用栈实现深度优先搜索:
```python
def dfs_stack(graph, start):
visited = set() # 用集合记录已经访问过的节点
stack = [start] # 用栈记录待访问的节点
while stack:
vertex = stack.pop() # 取出栈顶节点
if vertex not in visited:
visited.add(vertex) # 将节点标记为已访问
stack.extend(graph[vertex] - visited) # 将未访问的邻居节点加入栈中
return visited
```
用递归实现深度优先搜索:
```python
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next_vertex in graph[start] - visited:
dfs_recursive(graph, next_vertex, visited)
return visited
```
区别:
用栈实现深度优先搜索需要手动维护一个栈,将未访问的邻居节点加入栈中,然后取出栈顶节点进行访问。而用递归实现深度优先搜索则是通过递归函数的调用来实现的,不需要手动维护栈。但是在某些语言或者环境下,对规模较大的图使用递归思路会导致栈溢出。
深度优先搜索树代码 递归实现
以下是深度优先搜索树的递归实现代码,假设每个节点都有一个值和子节点列表:
```python
class TreeNode:
def __init__(self, val=0, children=None):
self.val = val
self.children = children if children is not None else []
def dfs(root):
if not root:
return
print(root.val)
for child in root.children:
dfs(child)
```
在这个代码中,我们首先检查根节点是否为空,如果是,我们直接返回。否则,我们打印根节点的值,并且对于每个子节点,递归地调用 `dfs` 函数。这将导致我们首先深入树的左侧分支,直到我们到达该分支的末端。然后,我们返回到父节点并进入下一个子节点,重复此过程,直到我们遍历了整个树。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)