大数据搜索，求助！

Question

假设每个QQ有好友100个，想找出其中任意两个QQ是否可以通过好友的好友的好友......而进行交流。
应该属于图的遍历，但是不管是深度遍历还是广度遍历，好像数据量都太大了
就算是只找出仅限于中间有10个联系人100*100*100*100*.....
感觉计算机也算不完啊：（
要实现这种功能数据库该如何设计，程序又该如何设计呢？
请大侠指点

Answer 1

感觉lz你的命题有点问题
细想下，任意两个ＱＱ能保证通过无限的＂好友＂而关连吗
比如：(= 表示好友关系，＜＞表示非好友关系）
a = b ;b = c; d = e; f = g;
如何能保证a,d,g三个ＱＱ中任何两个在好友关系中长出？
深度也好广度也好，从哪开始？
学习！

Answer 2

这个命题好像是网络状拓扑；
如果用start with / connect by 不行的话，
用中间临时表 t
insert t(id)
select distinct id from s
where s.id not in (
  select id from t
) and s.id in (
  select s2.fr_id from s s2
  inner join t where t.id= s2.id
))

Answer 3

sten(近视进士) 
我并没有说“任意两个ＱＱ能保证通过无限的＂好友＂而关连”，
我是说“任意两个QQ是否”，只是判断有没有这种连接的可能。

Answer 4

yaozw_mountain(山林) 运行时间可能会很长，如果只是查找通过一个中间人肯定没问题，但是中间联系人多了时间问题就出来了，就是100^n

Answer 5

select * from s s1
inner join s s2 where s2.id not in( s1.id ) and s2.id = s1.fr_id
inner join s s3 where s3.id not in( s1.id, s2.id ) and s3.id = s2.fr_id
inner join s s4 where s4.id not in( s1.id, s2.id, s3.id ) and s4.id = s3.fr_id
...
inner join s s10 where s10.id not in( s1.id, s2.id, s3.id,....s9.id ) and s10.id = s9.fr_id

Answer 6

要排除多余10的，可以用:
where not exist (
 select * from  s s11 where s11.id not in( s1.id, s2.id, s3.id,....s10.id ) and s11.id = s10.fr_id
)

Answer 7

如果任何记录永远存在id<>fr_id， 可以简化：
select * from s s1
inner join s s2 where s2.id = s1.fr_id
inner join s s3 where s3.id not in( s1.id ) and s3.id = s2.fr_id
inner join s s4 where s4.id not in( s1.id, s2.id ) and s4.id = s3.fr_id
...
inner join s s10 where s10.id not in( s1.id, s2.id, s3.id,....s8.id ) and s10.id = s9.fr_idwhere not exist (
 select * from  s s11 where s11.id not in( s1.id, s2.id, s3.id,....s9.id ) and s11.id = s10.fr_id
)

Answer 8

SELECT COUNT(*) FROM
(SELECT ID, FID FROM t 
START WITH id = 12345
CONNECT BY PRIOR ID = FID
)N1
WHERE ID = 67890先查找出 id = 12345 的所有可连通的好友，再看 id = 67890 是否属于该集合