为什么DFS和时间复杂度BFS O（V + E）

本文介绍了为什么DFS和时间复杂度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).