问SnapChat六度空间题

请教一下地里常出现的那道Snapchat六度空间题，
写一个函数，返回boolean，表示任意两个snapchat好友之间是不是可以通过最多6个中间好友认识
http://www.1point3acres.com/bbs/ ... ;highlight=snapchat
这个题面试官一直在要求的省空间是什么意思呢？
用DFS不是O（6）的空间复杂度么？ 虽然是暴力搜。。 时间复杂度是O（k^6）, k是每个人的好友数。。感觉时间复杂度也降不下去呀。。
还是我理解错题意了呢？ 求指点。。。

双向bfs时间o(2*k^3)

Onedayw 发表于 2016-11-9 11:55
双向bfs时间o(2*k^3)

懂了。那空间是O(k^3)吧？

小A要当码农 发表于 2016-11-9 11:56
懂了。那空间是O(k^3)吧？

对的 也是o(2*k^3)

Onedayw 发表于 2016-11-9 11:59
对的 也是o(2*k^3)

嗯嗯 多谢啊。 之前没想着要去优化时间复杂度。

看word ladder

关键双向bfs并不能省空间吧...
说dfs省空间的难道不算recursive stack吗....
双向dfs真心不知道怎么弄...

DFS 空间复杂度不应该是(6k)吗？