完成图的深度优先遍历算法、广度优先遍历算法。其中,邻接表的 创建相当于创建多个单链表。
时间: 2024-03-09 09:49:53 浏览: 64
好的,我可以帮你回答这个问题。
首先,我们先来看一下图的深度优先遍历算法(DFS):
```python
visited = set() # 存储已经访问过的节点
def dfs(graph, node):
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor)
```
其中,`graph` 表示邻接表,`node` 表示当前访问的节点。在函数中,我们首先判断当前节点是否已经被访问过,如果没有,则输出当前节点,并将其添加到 `visited` 集合中,然后递归访问当前节点的所有邻居节点。
接下来,我们再来看一下图的广度优先遍历算法(BFS):
```python
from collections import deque
def bfs(graph, start):
visited = set() # 存储已经访问过的节点
queue = deque([start]) # 存储待访问的节点
while queue:
node = queue.popleft()
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
queue.append(neighbor)
```
同样,`graph` 表示邻接表,`start` 表示起始节点。在函数中,我们使用 `deque` 来存储待访问的节点,然后依次从队列中取出节点,判断是否已经被访问过,如果没有,则输出当前节点,并将其添加到 `visited` 集合中,然后将当前节点的所有邻居节点加入到队列中。
至于邻接表的创建,可以使用一个字典来表示,其中字典的键表示节点,字典的值表示与该节点相邻的节点列表。例如:
```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'],
'E': ['C', 'D'],
'F': ['D']
}
```
这个邻接表表示了一个无向图,其中节点 A 与节点 B、C 相邻,节点 B 与节点 A、C、D 相邻,依此类推。
希望这个回答能够帮助到你,如果还有问题,请随时提出。
阅读全文