为什么DFS和时间复杂度BFS O（V + E） [英] Why is the time complexity of both DFS and BFS O( V + E )

问题描述

的基本算法BFS：

set start vertex to visited

load it into queue

    while queue not empty

        for each edge incident to vertex

             if its not visited

                 load into queue

                 mark vertex

所以，我觉得时间复杂度将是：

So I would think the time complexity would be:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

其中， v 是顶点 1 到 N

首先，是我说的话是否正确？其次，这是怎么 O（N + E），和直觉至于为什么将是非常好的。谢谢

Firstly, is what I've said correct? Secondly, how is this O(N + E), and intuition as to why would be really nice. Thanks

推荐答案

您总和

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

可改写为

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

和第一组是 O（N）而另一个是O（E）。

and the first group is O(N) while the other is O(E).

这篇关于为什么DFS和时间复杂度BFS O（V + E）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！