返回

算法-双向BFS的时间复杂度

发布时间:2022-06-22 01:31:10 243

传统(单向)BFS的时间复杂度为O(V+E)使用邻接列表时。双向BFS的情况是什么?

根据答案在这里,我知道:

  • BFS将穿过1+B+B^2+…+B^k顶点;鉴于
  • 双向BFS将穿过2+2B^2+…+2B^(k/2)个顶点。

但我不知道如何基于此导出时间复杂性。

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(1)
按点赞数排序
用户头像
相关帖子