邻接表的广度优先和深度优先
时间: 2023-11-24 16:53:10 浏览: 52
邻接表是一种图的表示方法,其中每个节点都与其相邻的节点列表相关联。广度优先搜索和深度优先搜索是两种常见的图遍历算法,可以用于在图中查找特定节点或路径。
邻接表的深度优先搜索(DFS):
深度优先搜索是一种递归算法,它从图的起始节点开始遍历,然后沿着路径尽可能远地访问每个节点,直到到达最远的节点,然后回溯以访问更多的节点。在邻接表中,可以使用递归函数来实现深度优先搜索。以下是一个示例代码:
```python
# 定义邻接表
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
# 定义深度优先搜索函数
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, 2)
```
输出结果为:2 0 1 3 。
邻接表的广度优先搜索(BFS):
广度优先搜索是一种迭代算法,它从图的起始节点开始遍历,然后逐层遍历每个节点的邻居,直到找到目标节点或遍历完整个图。在邻接表中,可以使用队列来实现广度优先搜索。以下是一个示例代码:
```python
# 定义邻接表
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
# 定义广度优先搜索函数
def bfs(graph, start):
visited, queue = set(), [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for next_node in graph[vertex]:
if next_node not in visited:
visited.add(next_node)
queue.append(next_node)
# 调用广度优先搜索函数
bfs(graph, 2)
```
输出结果为:2 0 3 1 。