树深度优先搜索python代码
时间: 2024-06-23 19:00:28 浏览: 8
当然,树的深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树和图的算法,它会尽可能深地搜索分支,直到到达叶子节点,然后回溯到上一个节点继续搜索。在Python中,你可以使用递归的方式来实现DFS。以下是一个简单的例子:
```python
class Node:
def __init__(self, value, children=None):
self.value = value
self.children = children if children is not None else []
# 假设你有一个Node类的实例表示树的结构
def dfs(node, visited=None):
if visited is None:
visited = set()
visited.add(node.value)
print(node.value, end=" ") # 打印当前节点值
for child in node.children:
if child not in visited: # 如果子节点未访问过
dfs(child, visited) # 递归调用DFS
return visited
# 示例使用
root = Node(1, [Node(2), Node(3), Node(4, [Node(5)])])
visited_nodes = dfs(root)
```
在这个例子中,`dfs`函数接收一个节点和一个已经访问过的集合`visited`(默认为空)。它首先检查当前节点是否已经被访问,如果没被访问,就添加到已访问集合,并打印节点值。接着,对于每个未访问过的子节点,它再次调用`dfs`函数。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)