Liveramp six-degree 问题

一会 准备做liveramp的online interview，
话说听说的六度问题（six-degree kevin bacon）哪位大大做过呢。。。

我自己怎么感觉很像all-pairs-shortest-paths O(|V|^3)的复杂度

为什么网上都是双向BFS什么的，那时间复杂度是O(b^(d/2))。。。怎么比较呢。、。算是多项式级的么

看LZ好像当年的自己，给LZ讲讲吧。

从source和target两头同时做BFS，复杂度就是O(b + b^2 + ... + b^(d/2))) = O(b^(d/2)))，b是平均每个点的neighbor数，d是遍历深度。这个显然polynomial time。

LZ给点分吧。

卧槽，还考这题？PIE最后一题，我觉得挺难就略过了。。。