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
v
1
n
首先,我所说的正确吗?其次,这是怎么回事O(N + E),以及关于其原因的直觉将非常好。谢谢
O(N + E)
你的钱
可以改写成
(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]
第一组是,O(N)而另一组是O(E)。
O(N)
O(E)