用python实现dfs遍历
时间: 2023-03-16 12:44:44 浏览: 177
可以使用以下Python代码实现深度优先搜索(DFS)遍历:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
相关问题
python实现深度遍历
深度遍历(Depth-First Search,DFS)是一种遍历图或树的算法,它从根节点开始遍历,沿着树的深度遍历子节点,当走到最深处时,再回溯到前一个节点,继续遍历其他子节点。以下是Python实现深度遍历的示例代码:
```python
# 定义节点类
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, node):
self.children.append(node)
# 深度遍历函数
def dfs(node):
print(node.value)
for child in node.children:
dfs(child)
# 测试代码
# 构建一棵树
root = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)
node8 = Node(8)
node9 = Node(9)
root.add_child(node2)
root.add_child(node3)
node2.add_child(node4)
node2.add_child(node5)
node3.add_child(node6)
node3.add_child(node7)
node4.add_child(node8)
node5.add_child(node9)
# 深度遍历树
dfs(root)
```
输出结果:
```
1
2
4
8
5
9
3
6
7
```
python 图的遍历dfs
深度优先搜索(Depth-First Search,DFS)是图论中的一个常用算法,用于遍历或搜索树和图的数据结构。在Python中,我们可以使用内置的数据结构和堆栈(stack)来实现DFS。以下是一个基本的DFS遍历图的例子,假设我们有一个用邻接列表表示的无向图:
```python
def dfs(graph, start_node):
visited = set() # 用于存储已经访问过的节点
stack = [start_node] # 初始化堆栈,将起始节点推入
while stack: # 只要堆栈不为空
node = stack.pop() # 弹出当前节点
if node not in visited: # 如果该节点未访问过
visited.add(node) # 标记为已访问
print(node, end=" ") # 输出节点值
# 推入未访问的邻居节点
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
# 假设我们有这样一个简单的图:
# graph = {
# 'A': ['B', 'C'],
# 'B': ['D', 'E'],
# 'C': ['F'],
# 'D': [],
# 'E': ['F'],
# 'F': []
# }
dfs(graph, 'A') # 从'A'开始遍历
```
运行上述代码,将按照DFS的方式输出节点序列:A B D E F C。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)