深度优先搜索 (DFS) 与广度优先搜索 (BFS) 伪代码和复杂性

我必须为计算连接数量的算法开发伪代码 给定顶点 V 和边 E，图中的分量 G = (V, E)。

我知道我可以使用深度优先搜索或广度优先搜索来计算连接组件的数量。

但是，我想使用最有效的算法来解决这个问题，但我不确定每个算法的复杂度。

下面是用伪代码形式编写 DFS 的尝试。

function DFS((V,E))
     mark each node in V with 0
     count ← 0
     for each vertex in V do
          if vertex is marked then
               DFSExplore(vertex)

function DFSExplore(vertex)
     count ← count + 1
     mark vertex with count
     for each edge (vertex, neighbour) do
          if neighbour is marked with 0 then
               DFSExplore(neighbour)

下面是用伪代码形式编写 BFS 的尝试。

function BFS((V, E))
     mark each node in V with 0
     count ← 0, init(queue)     #create empty queue 
     for each vertex in V do
          if vertex is marked 0 then
               count ← count + 1
               mark vertex with count
               inject(queue, vertex)             #queue containing just vertex
               while queue is non-empty do
                    u ← eject(queue)                          #dequeues u
                    for each edge (u, w) adjacent to u do
                         if w is marked with 0 then
                              count ← count + 1
                              mark w with count
                              inject(queue, w)     #enqueues w

我的讲师说BFS与DFS具有相同的复杂性。

然而，当我搜索深度优先搜索的复杂度时，它是 O(V^2)，而广度优先搜索的复杂度是使用邻接表时的 O(V + E)，使用邻接表时的复杂度是 O(V^2)。使用邻接矩阵。

我想知道如何计算 DFS / BFS 的复杂度，并且我想知道如何调整伪代码来解决问题。

如果使用邻接表，DFS 和 BFS 的时间复杂度是相同的，即 O(V+E)。因此，如果您问哪一个更好，那么这完全取决于您要解决的问题类型。假设您想要解决一个目标接近起始顶点的问题，那么 BFS 将是更好的选择。另外，如果考虑内存，那么 DFS 是更好的选择，因为不需要存储子指针。

图片提供 - Narasimha karumanchi 的 DSA Made Easy