广度优先遍历算法邻接表

以下是邻接表的广度优先遍历算法的Python实现：

from collections import deque
# 定义图的类
class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.adj = [[] for i in range(vertices)]  # 邻接表

    # 添加边
    def add_edge(self, u, v):
        self.adj[u].append(v)

    # 广度优先遍历
    def BFS(self, s):
        visited = [False] * self.V  # 记录每个顶点是否被访问过
        queue = deque()  # 辅助队列
        visited[s] = True
        queue.append(s)

        while queue:
            s = queue.popleft()
            print(s, end=" ")

            for i in self.adj[s]:
                if not visited[i]:
                    visited[i] = True
                    queue.append(i)

其中，Graph类表示一个图，包含顶点数和邻接表。add_edge方法用于向图中添加边，BFS方法用于进行广度优先遍历。visited数组用于记录每个顶点是否被访问过，queue是辅助队列，用于存储待访问的顶点。

举个例子，如果我们有以下邻接表表示的图：

0: 1 -> 2
1: 2 -> 3
2: 3
3: 4
4: 

其中，每一行表示一个顶点及其相邻的顶点。例如，第一行表示顶点0相邻的顶点为1和2。

我们可以使用以下代码进行广度优先遍历：

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)

print("BFS starting from vertex 0:")
g.BFS(0)

输出结果为：

BFS starting from vertex 0:
0 1 2 3 4