BFS (广度优先搜索) 和 DFS (深度优先搜索) 是两种常用的图遍历算法，它们在邻接矩阵和邻接表中的时间和空间复杂度如下：

1. 邻接矩阵：

邻接矩阵是一个二维数组，用于表示图中节点之间的连接关系。对于含有 n 个节点的图，邻接矩阵的大小为 n×n。

• BFS 时间复杂度：O(n^2)，需要遍历邻接矩阵中的所有节点，每个节点都需要检查与其他节点的连接关系，总共需要检查 n^2 次。

• BFS 空间复杂度：O(n)，需要一个队列来存储待访问的节点，最坏情况下队列中会存储所有的节点，因此空间复杂度为 O(n)。

• DFS 时间复杂度：O(n^2)，同样需要遍历邻接矩阵中的所有节点，每个节点都需要检查与其他节点的连接关系，总共需要检查 n^2 次。

• DFS 空间复杂度：O(n)，需要一个栈来存储待访问的节点，最坏情况下栈中会存储所有的节点，因此空间复杂度为 O(n)。

以下是在邻接矩阵中实现 BFS 和 DFS 的示例代码：

# BFS in adjacency matrix
def bfs(adj_matrix, start):
    n = len(adj_matrix)
    visited = [False] * n
    queue = [start]
    visited[start] = True

    while queue:
        node = queue.pop(0)
        print(node, end=' ')

        for neighbor in range(n):
            if adj_matrix[node][neighbor] and not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# DFS in adjacency matrix
def dfs(adj_matrix, start):
    n = len(adj_matrix)
    visited = [False] * n
    stack = [start]

    while stack:
        node = stack.pop()
        if not visited[node]:
            print(node, end=' ')
            visited[node] = True

            for neighbor in range(n-1, -1, -1):
                if adj_matrix[node][neighbor] and not visited[neighbor]:
                    stack.append(neighbor)

2. 邻接表：

邻接表是一种更加紧凑的图表示方法，它使用链表数组来表示图中每个节点的邻居。对于含有 n 个节点的图，邻接表的大小为 n。

• BFS 时间复杂度：O(n+m)，其中 m 表示边的数量。BFS 需要遍历邻接表中的所有节点，并访问其所有邻居。在最坏情况下，每个节点都与其他节点都有边相连，因此需要访问 m 个邻居。

• BFS 空间复杂度：O(n)，需要一个队列来存储待访问的节点，最坏情况下队列中会存储所有的节点，因此空间复杂度为 O(n)。

• DFS 时间复杂度：O(n+m)，同样需要遍历邻接表中的所有节点，并访问其所有邻居，最坏情况下需要访问 m 个邻居。

• DFS 空间复杂度：O(n)，需要一个栈来存储待访问的节点，最坏情况下栈中会存储所有的节点，因此空间复杂度为 O(n)。

以下是在邻接表中实现 BFS 和 DFS 的示例代码：

# BFS in adjacency list
def bfs(adj_list, start):
    n = len(adj_list)
    visited = [False] * n
    queue = [start]
    visited[start] = True

    while queue:
        node = queue.pop(0)
        print(node, end=' ')

        for neighbor