用邻接表实现图的遍历

使用邻接表实现图的遍历可以分为深度遍历和广度遍历两种方式。具体实现方法如下：

1.深度遍历

深度遍历使用栈来实现，具体步骤如下：

（1）从起始节点开始，将其标记为已访问，并将其入栈。

（2）从栈中取出一个节点，遍历其所有未被访问的邻接点，将其标记为已访问，并将其入栈。

（3）重复步骤（2），直到栈为空。

def DFS(graph, start):
    visited = set() # 用集合来存储已访问的节点
    stack = [start] # 用列表来模拟栈
    while stack:
        node = stack.pop() # 取出栈顶节点
        if node not in visited:
            visited.add(node) # 标记为已访问
            print(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor) # 将未访问的邻接点入栈

2.广度遍历

广度遍历使用队列来实现，具体步骤如下：

（1）从起始节点开始，将其标记为已访问，并将其入队。

（2）从队列中取出一个节点，遍历其所有未被访问的邻接点，将其标记为已访问，并将其入队。

（3）重复步骤（2），直到队列为空。

from collections import deque

def BFS(graph, start):
    visited = set() # 用集合来存储已访问的节点
    queue = deque([start]) # 用双端队列来模拟队列
    while queue:
        node = queue.popleft() # 取出队首节点
        if node not in visited:
            visited.add(node) # 标记为已访问
            print(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor) # 将未访问的邻接点入队