传递闭包 BFS 解法复杂度?
  • 板块灌水区
  • 楼主typerxiaozhu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/23 17:54
  • 上次更新2024/3/23 17:54:56
查看原帖
传递闭包 BFS 解法复杂度?
807832
typerxiaozhu楼主2024/3/23 17:54

想到一个问题,假如枚举每一个点,然后跑一遍 BFS,然后把能遍历到的点都标记掉,是否也能做传递闭包呢?遍历图的复杂度是 O(n+m)O(n+m),枚举每个点的复杂度是 O(n)O(n),乘起来比 O(n3)O(n^3) 小?什么情况,我漏算了什么?

2024/3/23 17:54
加载中...