dfs算法python
时间: 2024-04-20 10:21:19 浏览: 10
深度优先搜索(DFS)是一种常用的图遍历算法,用于遍历或搜索图或树的所有节点。在DFS中,从起始节点开始,沿着一条路径尽可能深入地探索,直到无法继续为止,然后回溯到上一个节点,继续探索其他路径。以下是DFS算法的Python实现:
```python
# 定义图的类
class Graph:
def __init__(self):
self.graph = {}
# 添加边
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
# DFS遍历
def dfs(self, start):
visited = set() # 用于记录已访问的节点
self._dfs(start, visited)
# 内部递归函数
def _dfs(self, node, visited):
visited.add(node)
print(node, end=" ")
if node in self.graph:
for neighbor in self.graph[node]:
if neighbor not in visited:
self._dfs(neighbor, visited)
```
使用示例:
```python
# 创建图对象
g = Graph()
# 添加边
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 6)
# 从节点1开始进行DFS遍历
print("DFS遍历结果:")
g.dfs(1)
```
输出结果:
```
DFS遍历结果:
1 2 4 5 3 6
```