【图的周游算法】深度优先算法和广度优先算法
时间: 2023-12-15 19:33:00 浏览: 44
以下是深度优先算法和广度优先算法的介绍和演示:
深度优先算法(Depth First Search,DFS):
深度优先算法是一种用于遍历或搜索树或图的算法。它从根节点开始,沿着一条路径尽可能远地遍历每个节点,然后回溯到前一个节点,尝试另一条路径,直到所有节点都被访问为止。深度优先算法使用栈来实现,因此也称为“栈搜索”。
以下是一个使用深度优先算法遍历图的Python代码示例:
```python
# 定义图的邻接表表示法
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 深度优先遍历函数
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_node in graph[start]:
if next_node not in visited:
dfs(graph, next_node, visited)
# 调用深度优先遍历函数
dfs(graph, 'A')
```
输出结果为:A B D E F C
广度优先算法(Breadth First Search,BFS):
广度优先算法是一种用于遍历或搜索树或图的算法。它从根节点开始,逐层遍历每个节点,直到找到目标节点或遍历完整个图。广度优先算法使用队列来实现。
以下是一个使用广度优先算法遍历图的Python代码示例:
```python
# 定义图的邻接表表示法
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 广度优先遍历函数
def bfs(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
node = queue.pop(0)
print(node, end=' ')
for next_node in graph[node]:
if next_node not in visited:
visited.add(next_node)
queue.append(next_node)
# 调用广度优先遍历函数
bfs(graph, 'A')
```
输出结果为:A B C D E F
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![](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)