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

• Z时代
• 2024-01-10
• 分类：问答

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)，以及关于其原因的直觉将非常好。谢谢

回答：

你的钱

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)。

以上是 为什么DFS和BFS的时间复杂度为O（V + E） 的全部内容， 来源链接： utcz.com/qa/430202.html