实验4 图的遍历算法的设计与实现

图的遍历算法是指按照某种规则依次访问图中每个顶点的过程，常用的两种遍历算法分别是深度优先遍历（DFS）和广度优先遍历（BFS）。

1. 深度优先遍历（DFS）

深度优先遍历是一种递归的遍历方式，从某个顶点出发，沿着一条路径尽可能深地访问顶点，直到该路径到达最后一个顶点。然后回溯到前一个顶点，继续访问其他未被访问过的顶点，直到所有顶点都被访问完为止。

深度优先遍历的实现代码：

def dfs(graph, start, visited):
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)

其中，`graph` 是图的邻接表表示，`start` 是遍历的起始顶点，`visited` 是已经访问过的顶点集合。

2. 广度优先遍历（BFS）

广度优先遍历是一种按层次逐个访问顶点的遍历方式，从某个顶点出发，先访问其所有相邻的顶点，然后再访问相邻顶点的相邻顶点，以此类推，直到所有顶点都被访问完为止。

广度优先遍历的实现代码：

from collections import deque

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

其中，`graph` 是图的邻接表表示，`start` 是遍历的起始顶点，`visited` 是已经访问过的顶点集合，`queue` 是用于存储待访问顶点的队列。