使用邻接表来表示图的结构，Python 代码演示邻接表的深度优先遍历和广度优先遍历的实现。

# 深度优先搜索（Depth-First Search, DFS）算法函数
# 使用集合来记录已经访问过的节点，在遍历过程中递归访问每个节点的邻居节点，并打印访问顺序。
def dfs(graph, start, visited=None):
    # 若visited参数未提供，则初始化为None
    if visited is None:
        # 使用集合存储已访问的节点，确保每个节点只被访问一次
        visited = set()
    
    # 将当前起始节点添加到已访问节点集合中
    visited.add(start)
    
    # 打印当前节点，表示访问了该节点
    print(start)
    
    # 遍历当前节点的邻居节点
    for neighbor in graph[start] - visited:
        # 对未访问过的邻居节点进行递归调用DFS函数
        dfs(graph, neighbor, visited)
    
    # 返回最终访问过的所有节点集合
    return visited

# 定义图的邻接表结构
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

# 从'A'节点开始执行深度优先搜索
dfs(graph, 'A')


print('----------------------------------')


# 广度优先搜索（Breadth-First Search, BFS）算法函数
# 利用双端队列和集合数据结构实现了广度优先搜索的原理，按照逐层扩展探索的方式遍历整个图并输出访问顺序。
from collections import deque

def bfs(graph, start):
    # 使用集合存储已访问的节点，确保每个节点只被访问一次
    visited = set()
    
    # 使用双端队列（deque）来实现BFS的队列结构，从起始点开始探索
    queue = deque([start])
    
    # 将起始节点标记为已访问
    visited.add(start)
    
    # 当队列不为空时循环执行BFS
    while queue:
        # 从队列左侧取出顶点作为当前节点
        vertex = queue.popleft()
        
        # 打印当前节点，表示访问了该节点
        print(vertex)
        
        # 遍历当前节点的邻居节点
        for neighbor in graph[vertex] - visited:
            # 将未访问过的邻居节点加入已访问集合和队列中
            visited.add(neighbor)
            queue.append(neighbor)

# 定义图的邻接表结构
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

# 从'A'节点开始执行广度优先搜索
bfs(graph, 'A')

简要解释一下这两种遍历算法的原理和代码实现。

深度优先遍历算法原理：

深度优先遍历 (Depth First Search, DFS) 是一种用于遍历或搜索树或图的算法。在这种遍历过程中，从起始顶点开始，沿着路径一直走到最深处，直到不能再前进为止，然后返回上一级，继续探索未被访问的分支。这一过程是递归的。深度优先遍历在图中一般使用栈来实现。

深度优先遍历算法实现：

1. 创建一个布尔数组 visited[]，用于记录顶点是否已被访问过。
2. 从给定的起始顶点开始，递归地遍历该顶点的所有未访问过的邻接顶点。
3. 在访问每个顶点时，将其标记为已访问，并递归地遍历其邻接顶点。
4. 重复以上步骤，直到所有可达的顶点都被访问过。

广度优先遍历算法原理：

广度优先遍历 (Breadth First Search, BFS) 也是一种用于遍历或搜索树或图的算法。在这种遍历过程中，从起始顶点开始，依次访问该顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，以此类推，直到图中所有可达顶点都被访问。广度优先遍历一般使用队列来实现。

广度优先遍历算法实现：

1. 创建一个布尔数组 visited[]，用于记录顶点是否已被访问过。
2. 创建一个空队列 queue，用于存储待访问的顶点。
3. 将起始顶点加入队列，并标记为已访问。
4. 从队列中取出一个顶点，访问其所有未被访问过的邻接顶点，并将这些邻接顶点加入队列中。
5. 重复以上步骤，直到队列为空。

这两种遍历算法都具有其独特的应用场景和优劣势，选择哪种算法取决于具体问题的要求和性质。

-------------------

这段代码定义了一个图(Graph)类，实现了图的深度优先搜索(DFS)和广度优先搜索(BFS)算法。使用邻接表来表示图的结构。下面是对代码中各个部分的详细注释：

• __init__(self): 类的初始化方法，初始化一个空的邻接表图。

• add_edge(self, u, v): 添加边的方法，将顶点u和v之间的边加入图中。

• dfs_util(self, v, visited): 深度优先搜索的辅助方法，以顶点v为起点进行深度优先搜索，并标记已访问过的顶点。

• dfs(self, v): 深度优先搜索方法，以顶点v为起点进行深度优先搜索。

• bfs(self, v): 广度优先搜索方法，以顶点v为起点进行广度优先搜索。

在下面的代码部分，首先创建了两个图实例，分别进行了深度优先搜索和广度优先搜索，并输出了搜索结果。

from collections import defaultdict

class Graph:
    def __init__(self):
        # 使用 defaultdict(list) 创建了一个默认值为列表的字典，用于存储图的邻接表
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        """
        添加边的方法
        :param u: 边的起始顶点
        :param v: 边的终止顶点
        """
        self.graph[u].append(v)  # 将终止顶点添加到起始顶点的邻接列表中

    def dfs_util(self, v, visited):
        """
        深度优先搜索的辅助函数
        :param v: 当前顶点
        :param visited: 用于标记顶点是否已被访问的列表
        """
        visited[v] = True  # 将当前顶点标记为已访问
        print(v, end=' ')  # 打印当前顶点

        for i in self.graph[v]:
            if not visited[i]:
                self.dfs_util(i, visited)  # 递归调用深度优先搜索函数访问当前顶点的未访问邻接顶点

    def dfs(self, v):
        """
        深度优先搜索方法
        :param v: 搜索起始顶点
        """
        visited = [False] * (max(self.graph) + 1)  # 创建标记列表，初始时所有顶点均未被访问
        self.dfs_util(v, visited)  # 调用深度优先搜索辅助函数

    def bfs(self, v):
        """
        广度优先搜索方法
        :param v: 搜索起始顶点
        """
        visited = [False] * (max(self.graph) + 1)  # 创建标记列表，初始时所有顶点均未被访问
        queue = []  # 创建空队列，用于存储待访问顶点
        queue.append(v)  # 将起始顶点加入队列
        visited[v] = True  # 将起始顶点标记为已访问

        while queue:
            v = queue.pop(0)  # 取出队列中的第一个顶点
            print(v, end=' ')  # 打印当前访问的顶点

            for i in self.graph[v]:
                if not visited[i]:
                    queue.append(i)  # 将未访问过的邻接顶点加入队列
                    visited[i] = True  # 标记邻接顶点为已访问

# 邻接表的深度遍历
print("邻接表的深度遍历:")
g_dfs = Graph()
g_dfs.add_edge(0, 1)
g_dfs.add_edge(0, 2)
g_dfs.add_edge(1, 2)
g_dfs.add_edge(2, 0)
g_dfs.add_edge(2, 3)
g_dfs.add_edge(3, 3)

g_dfs.dfs(2)  # 从顶点2开始深度优先遍历

print("\n")

# 邻接表的广度遍历
print("邻接表的广度遍历:")
g_bfs = Graph()
g_bfs.add_edge(0, 1)
g_bfs.add_edge(0, 2)
g_bfs.add_edge(1, 2)
g_bfs.add_edge(2, 0)
g_bfs.add_edge(2, 3)
g_bfs.add_edge(3, 3)

g_bfs.bfs(2)  # 从顶点2开始广度优先遍历

解释一下def bfs(self, v):的功能：

1. bfs(self, v): 这是一个类方法，用于执行广度优先搜索。它接受一个参数 v，表示搜索的起始顶点。

2. visited = [False] * (max(self.graph) + 1): 创建一个布尔类型的列表 visited，用于标记顶点是否已被访问过。列表的长度为图中顶点编号的最大值加一，初始化所有元素为 False。

3. queue = []: 创建一个空队列，用于存储待访问的顶点。

4. queue.append(v): 将起始顶点 v 加入队列，并将其标记为已访问。

5. while queue:: 当队列不为空时，执行循环，表示还有顶点需要被访问。

6. v = queue.pop(0): 从队列中取出一个顶点 v，并将其从队列中移除。这里使用 pop(0) 表示从队列的头部取出元素，即先进先出。

7. print(v, end=' '): 打印当前访问的顶点 v。

8. for i in self.graph[v]:: 遍历当前顶点 v 的所有邻接顶点。

9. if not visited[i]:: 如果邻接顶点 i 还未被访问过，则将其加入队列，并标记为已访问。

这样，通过不断将邻接顶点加入队列，直到队列为空，就完成了广度优先搜索算法的执行过程。在执行过程中，顶点的访问顺序按照它们距离起始顶点的距离逐层增加，因此可以实现广度优先的搜索策略。