Python实现深度搜索和广度搜索算法,具体代码案例
时间: 2023-04-04 10:03:58 浏览: 117
可以使用Python实现深度搜索和广度搜索算法。以下是具体的代码案例:
深度搜索算法:
```python
def dfs(graph, start, end):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex == end:
return True
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return False
```
广度搜索算法:
```python
from collections import deque
def bfs(graph, start, end):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex == end:
return True
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return False
```
其中,graph表示图的邻接表,start表示起点,end表示终点。在深度搜索算法中,使用了栈来实现深度优先搜索;在广度搜索算法中,使用了队列来实现广度优先搜索。
阅读全文