深度优先搜索 (DFS) 与广度优先搜索 (BFS) 伪代码和复杂度 [英] Depth first search (DFS) vs breadth first search (BFS) pseudocode and complexity

问题描述

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

I have to develop pseudocode for an algorithm that computes the number of connected components in a graph G = (V, E) given vertices V and edges E.

我知道我可以使用深度优先搜索或广度优先搜索来计算连通分量的数量.

I know that I can use either depth-first search or breadth-first search to calculate the number of connected components.

然而，我想用最高效的算法来解决这个问题，但我不确定每个算法的复杂度.

However, I want to use the most efficient algorithm to solve this problem, but I am unsure of the complexity of each algorithm.

下面尝试以伪代码形式编写 DFS.

Below is an attempt at writing DFS in pseudocode form.

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.

Below is an attempt at writing BFS in pseudocode form.

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 具有相同的复杂性.

My lecturer said that BFS has the same complexity as DFS.

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

However, when I searched up the complexity of depth-first search it was O(V^2), while the complexity of breadth-first search is O(V + E) when adjacency list is used and O(V^2) when adjacency matrix is used.

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

I want to know how to calculate the complexity of DFS / BFS and I want to know how I can adapt the pseudocode to solve the problem.

推荐答案

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

Time complexity for both DFS & BFS is same i.e O(V+E) if you're using adjacency list. So if you ask, which one is better then it completely depends on the type of problem you are going to solve. Let's say you want to solve a problem where you have your goal near the starting vertex then BFS would be a better choice. Plus, if you consider memory then DFS is a better option because there is no need of storing child pointers.

图片提供 - Narasimha karumanchi 的 DSA Made Easy

Image courtesy - DSA Made Easy by Narasimha karumanchi

这篇关于深度优先搜索 (DFS) 与广度优先搜索 (BFS) 伪代码和复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！