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

Question

我必须为计算连接数的算法开发伪代码 图 G = (V, E) 中的分量给定顶点 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 的复杂度，我想知道如何调整伪代码来解决问题。

Answer 1

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

图片由 Narasimha karumanchi 提供 - DSA 变得简单