一尘不染

为什么DFS和BFS的时间复杂度为O(V + E)

algorithm

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

所以我认为时间复杂度是:

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

v顶点1在哪里n

首先,我所说的正确吗?其次,这是怎么回事O(N + E),以及关于其原因的直觉将非常好。谢谢


阅读 966

收藏
2020-07-28

共1个答案

一尘不染

你的钱

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)

2020-07-28