怎么样Python实现dfs和bfs爬行策略
时间: 2024-09-24 10:29:39 浏览: 19
在Python中,深度优先搜索(DFS,Depth First Search)和广度优先搜索(BFS,Breadth First Search)通常用于网络爬虫(Web Crawling)中的节点遍历。以下是简单的Python实现:
### 深度优先搜索(DFS)
```python
from collections import deque
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop() # 弹出栈顶元素
if vertex not in visited:
print(vertex) # 访问节点
visited.add(vertex)
# 添加未访问的邻居到栈顶
neighbors = graph[vertex] if isinstance(graph[vertex], list) else graph[vertex].neighbors
for neighbor in neighbors:
if neighbor not in visited:
stack.append(neighbor)
# 示例用法:
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
dfs(graph, 'A')
```
### 广度优先搜索(BFS)
```python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start]) # 使用双端队列存储节点
while queue:
vertex = queue.popleft() # 弹出队首元素
if vertex not in visited:
print(vertex) # 访问节点
visited.add(vertex)
# 将未访问的邻居添加到队列尾部
neighbors = graph[vertex] if isinstance(graph[vertex], list) else graph[vertex].neighbors
for neighbor in neighbors:
if neighbor not in visited:
queue.append(neighbor)
# 示例用法:
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': [], 'F': []}
bfs(graph, 'A')
```
在这两个示例中,`graph`是一个表示网络结构的字典,其中键是节点名,值可以是列表(表示有向图)或包含邻居的属性(表示无向图)。`start`是开始遍历的起始节点。