关于6度的一个算法

xtfvvv

表结构如下,就两个字段

user char(10)   //用户
friend char(10) //这个用户的朋友(们)


数据demo:
   user  friend
--------------------
   alex  tom
   alex  john
   alex  diana
   john  simeno
   john  cooker
   john  coco
   wendy kk47
   wendy stephen

随便从user列中取出两个用户,如何判断他们是否可以从朋友,以及朋友的朋友,或者朋友的朋友的朋友可以联系上?
   比如alex可以通过朋友john认识coco, 但是alex没有办法可以联系倒stephen.数据量比较大的时候,应该用什么算法?

   这应该算是图的连通性问题吧?

fangaibi

恩，就是连通性！
1，如果要知道任何2人之间是不是可以到达O(1)时间内知道，小弟我只想到O(n^3)的算法，传递闭包可以，弗洛伊德也可以，只需稍微改一下！
2，当然如果不需要在O(1)时间内判断，则可以把图分成几个连通的集合，这个可以考虑生成树方法(没必要最小生成树)，dfs 也可以，具体情况而定了，这个创建的复杂度就低了
如果图变化不多，主要是查询，还是用1，反之用2

小弟只能想到这些，期待更高效的算法

ivor1982

并查集，查找时间几乎O(1)

xiaobaixi

本人乱哈啦的...


如果只为了   查询O(1)
可以先把所有人    建立一个矩阵

如图:
  A B C D E F
A
B
C
D
E
F

然后就计算他们的关系
那么
下次查询就只需要查矩阵可知了

guess12300

见贴就顶

lhc6847069

ivor1982正解
并查集。
查找时间就是O(1)

输入要O(n)就是咯.哈哈。