python 图结构
时间: 2023-12-17 11:29:15 浏览: 34
以下是Python中图结构的深度搜索和广度搜索的例子:
1. 深度搜索主体
```python
def dfs(graph, path, end, results, w, weights):
# 找出从start到end的所有路径
s = path[-1]
if s == end:
# 判断是否走到指定位置
results.append(path) # 添加路径
weights.append(w) # 添加路径权重
return
for x in graph[ord(s) - 65]:
if x not in path:
# 走过的不再走
dfs(graph, path + [x], end, results, w + graph[ord(s) - 65][x], weights)
# 这里注意不能path.append(x),因为path会跟着变
```
2. 广度搜索主体
```python
from queue import Queue
def bfs(graph, start):
# 遍历图
queue = Queue()
search = [] # 用来记录已经搜索过的
queue.put(start)
print(start)
search.append(start)
while not queue.empty():
s = queue.get()
for i in graph[ord(s) - 65]:
if i not in search:
queue.put(i)
print(i)
search.append(i)
```