深度优先搜索（DFS）与广度优先搜索（BFS）伪码和复杂性

Question

我必须为一个算法开发伪代码，该算法计算给定顶点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的复杂度，我想知道如何修改伪代码来解决这个问题。

Answer 1

两个DFS的时间复杂度

图片提供-Narasimha Karumachi轻松完成DSA