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)
where v是顶点1 to n
首先我说的对吗？其次，这是怎么回事O(N + E)，以及关于为什么的直觉会非常好。谢谢
Your sum
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).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
