我的复杂度是这样算的：BF复杂度为O(VE),最差情况下E为V^2级别的，所以O(VE)=O(V^3)；
如果再对每个顶点调用一次就是O(V^3)*O(V)=O(V^4)了。
当然我用的是朴素的方法，没有加入优先队列什么的优化。。。。所以每一次调用算法都要对图中每一条边（哪怕是图中不存在的边，我是用长度INF进行标记）都会历遍，这么以来复杂度就比较高了。。。。
所以这个上界只是一个松的上界，可能会比实际的渐进复杂度量级会大一些。
我貌似理解你的意思了，你是说最后总的复杂度由图中最大的连通分量中的顶点数V决定，所以即使对每个点（当然是上一次算法调用中未访问到的点）都调用一次BF，总的复杂度最多还是O(V^3)么？
不知道我理解的对不对？还请指教。
谢谢回答我的问题哈O(∩_∩)O~

• Re:你这复杂度是闹哪样... (407) braveTester 2012-03-22 23:39:51
  • Re:你这复杂度是闹哪样... (51) jwpan 2012-07-19 23:20:53