图的遍历深度和广度代码

图的遍历是指访问图的所有节点的过程，常用的两种遍历方法是深度优先搜索（DFS）和广度优先搜索（BFS）。在图的遍历中，深度优先搜索和广度优先搜索具有不同的优缺点，因此在实际应用中，选择相应的遍历方法要视情况而定。

深度优先搜索是从起始点开始，一直沿着一条未访问过的路径尽可能深入图中的节点，直到无法继续为止，然后回溯到前一个节点，继续搜索下一条未访问过的路径。深度优先搜索实现简单，只需要一个栈来存储节点访问的顺序，并且对于具有一定深度的图，深度优先搜索的速度比广度优先搜索快。但是深度优先搜索容易陷入局部最优解，因此对于求解全局最优解的问题来说，不是很适用。

广度优先搜索是从起始点开始，一层一层地访问图中的所有节点，直到所有节点都被访问过。广度优先搜索需要一个队列来存储节点的访问顺序，对于对于求解全局最优解的问题，广度优先搜索的效果比深度优先搜索好。但是它的空间复杂度比较大，需要存储所有被访问的节点，因此对于大规模的图来说，空间开销比较大。

以下是深度优先搜索和广度优先搜索的代码实现：

深度优先搜索的代码：

```

visited = set()

def dfs(node):

visited.add(node)

# 处理节点 node

for next_node in node.children():

if next_node not in visited:

dfs(next_node)

```

广度优先搜索的代码：

```

def bfs(start, end):

q = []

q.append([start])

visited.add(start)

while q:

path = q.pop(0)

last_node = path[-1]

# 处理节点last_node

if last_node == end:

# 返回结果

for next_node in last_node.children():

if next_node not in visited:

visited.add(next_node)

new_path = path + [next_node]

q.append(new_path)

```

在实际应用中，如何选择深度优先搜索和广度优先搜索要视情况而定，以下是一些常见的情况：

1. 如果目标是找到一条路径，那么可以使用深度优先搜索。例如迷宫问题中，从起点到终点的路径也是深度优先搜索的典型应用。

2. 如果目标是找到最短路径或最小代价，那么可以使用广度优先搜索。

3. 如果图比较稠密，即节点之间的边比较多，那么使用深度优先搜索的空间开销会更小。反之，如果图比较稀疏，即节点之间的边比较少，那么使用广度优先搜索的时间开销会更小。

总之，深度优先搜索和广度优先搜索各有优缺点，选择哪种方法要根据实际问题来决定。