用DFS和BFS分别列出其所有的连通集的时间复杂度

DFS 和 BFS 都可以用来列出图中的连通集。

使用 DFS，我们可以从任意一个未访问过的节点开始遍历，遍历到的节点都属于同一个连通集。我们可以递归地访问每个节点，标记它们为已访问，并将它们加入到当前连通集中。当无法继续递归时，说明当前连通集已经遍历完成，我们可以将它存储下来。重复以上步骤，直到所有的节点都被访问过。

时间复杂度为 O(n+m)，其中 n 是节点数，m 是边数。这是因为我们需要访问每个节点和每条边恰好一次。

使用 BFS，我们可以从任意一个未访问过的节点开始遍历，遍历到的节点都属于同一个连通集。我们可以将当前节点加入到队列中，并标记它为已访问。接着，我们从队列中取出一个节点，访问它的所有未访问过的邻居节点，并将它们加入到队列中。当队列为空时，说明当前连通集已经遍历完成，我们可以将它存储下来。重复以上步骤，直到所有的节点都被访问过。

时间复杂度为 O(n+m)，其中 n 是节点数，m 是边数。这是因为我们需要访问每个节点和每条边恰好一次，而每个节点和每条边都会被加入到队列中恰好一次。

相关问题

dfs与bfs时间复杂度

### DFS与BFS时间复杂度分析

#### 深度优先搜索（DFS）

对于深度优先搜索，在最坏情况下，同样可能需要访问所有的节点和边来完成整个图的遍历。假设图中有 \(V\) 个顶点和 \(E\) 条边，则其时间复杂度主要取决于对每个顶点及其相邻边的操作次数。

- 对于无向图而言，每条边会被两个端点各处理一次；因此，总的运行时间为 \(\Theta(V+E)\)[^1]。
- 如果是稀疏图（即\(E=O(V)\)，意味着边数大约等于或小于顶点数目），那么该算法效率较高；
- 而对于稠密图（当接近完全连通时，\(|E|\approx|V|^2\)），尽管如此，由于只需要线性时间内完成操作，性能依然可以接受。

#### 广度优先搜索（BFS）

广度优先搜索在最坏的情况下也会遍历整张图中的每一个节点以及它们之间的连接关系。考虑到这一点：

- 类似地，如果采用邻接表表示法，BFS 的时间复杂度也是 \(\Theta(V+E)\)。
- 这是因为 BFS 需要检查每个顶点并探索它所关联的所有边，直到找到目标为止或者所有可达区域都被覆盖完毕。

值得注意的是，上述两种方法的时间复杂度表达形式相同，但在实际应用中会因为具体场景的不同而有所差异。例如，在某些特定结构的数据集上，一种可能会比另一种表现得更好。

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)

        if vertex not in visited:
            visited.add(vertex)
            queue.extend(
                neighbor for neighbor in graph[vertex] if neighbor not in visited
            )

    return visited


def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)

    for next_vertex in graph[start] - visited:
        dfs(graph, next_vertex, visited)

    return visited