实现图的深度优先遍历和广度优先遍历

深度优先遍历（Depth First Search，DFS）和广度优先遍历（Breadth First Search，BFS）都是图的常见遍历算法。下面我将简单介绍它们的实现方法。

（1）深度优先遍历

深度优先遍历是一种递归遍历方式，首先访问起始顶点，然后依次访问与该顶点相邻的未被访问的顶点，重复该操作，直到所有顶点都被访问过。具体步骤如下：

1. 首先访问起始顶点；
2. 遍历与该顶点相邻的未被访问的顶点；
3. 对于每个相邻的未被访问的顶点，以该顶点为起始顶点，递归执行上述两个步骤。

以下是深度优先遍历的 Python 代码实现：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_vertex in graph[start] - visited:
        dfs(graph, next_vertex, visited)
    return visited

其中，graph 表示图的邻接表，start 表示起始顶点，visited 表示已经访问过的顶点。代码中，使用了 Python 的 set 类型来存储 visited 集合。

（2）广度优先遍历

广度优先遍历是一种非递归遍历方式，首先访问起始顶点，然后依次访问与该顶点相邻的未被访问的顶点，重复该操作，直到所有顶点都被访问过。具体步骤如下：

1. 首先访问起始顶点；
2. 将起始顶点加入队列；
3. 取出队列中的一个顶点，并遍历与该顶点相邻的未被访问的顶点，将这些顶点加入队列；
4. 对队列中的每个顶点，重复步骤3，直到所有顶点都被访问过。

以下是广度优先遍历的 Python 代码实现：

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

其中，graph 表示图的邻接表，start 表示起始顶点。代码中，使用了 Python 的 deque 类型来实现队列。