郝聪SEO博客：SEO顾问咨询服务公司

【最短路径】  åœ†æ˜Žå›­çš„北部有一个迷宫，据说古时候每次有庆典在圆明园的时候，皇帝会派一些宫女走迷宫，看谁最先走到迷宫内的亭子，会有不错的奖赏。  è¿·å®«é—®é¢˜å¯¹æ•°å­¦å®¶ä»¬æ¥è®²è™½ç„¶æ˜¯å°å„¿ç§‘但在计算机课程上却非常重要，因为不同的求解会涉及到递归，广度优先和深度优先等算法。  è¿·å®«æ¯•ç«Ÿæ˜¯ä¸€ä¸ªæ”¾ç½®åœ¨2维空间的有限联系的网络，也就是说，迷宫里的每一个点，最多只和周围的4个点(上下左右)发生关系，而且这些点的位置是固定的。  

六度分割通常用来描述一个广阔的社会网路（SN），现在大部分的社会网路服务都提供了搜索功能，即搜索出一个用户到达另外一个用户的最短路径，也就是找出这两个用户之间通过最少的用户的链接。  ä¸€èˆ¬çš„SN提供的搜索都是4度的，也就是例如A-B-C-D-E 称为4度的分隔。提供5度搜索和6度搜索的几乎寥寥无几，当然一方面是5，6度分隔的用户很少，大部分的用户都应该在4度内，另外一个方面是5，6度分隔的搜索在实际计算上也涉及非常大的运算量。  

【SN搜索算法】  å¦‚果说寻找两个人之间的最小分隔的路径和寻找最短路径可以类比，那么唯一不同的是SN上每个节点的联系可以非常的广阔，不只是上下左右，而是十个甚至上百个联系。这是是一个多维空间内的最短路径的寻找。假设一个用户平均有n个好友，那么粗略估计一个用户的4度好友大约有n×n×n×n＋n×n×n+n×n+n ~ n^4，无疑是一个非常恐怖的数目。因此采用传统的递归的方法显然是不大现实的。  å½“然，事情并非这么麻烦，有简洁的方法可以加快找到用户之间的最小分隔：不单是从一个用户搜索，而是从两个用户同时搜索，而看两个用户的2度之内的用户是否有相同： A-B-C E-D-C Aå’ŒE的处在在两度分隔的用户基本上数目估计都在n的平方。问题变成了比较n^2å’Œn^2之间有没有相同，这个计算的时间等同于2×n^2的排序所需要的时间。

【SN索引】  é‚£ä¹ˆèƒ½å¦ç»§ç»­åŠ å¿«é€Ÿåº¦ï¼Ÿ 当然可以，可以提前对用户的好友进行索引，对好友的好友进行索引，这样在未来进行关系的搜索时会大大加快：  A: {A1} {A2} A1为A的好友的集合，A2为A的好友的好友的集合 E: {E1} {E2}  é‚£ä¹ˆ 1度分隔为： A 属于｛E1｝，等同于E属于 {A1} 2度分隔为： A 属于｛E2｝，等同于E属于 {A2}，{A1}{E1}有共同项。 3度分隔为： {A1} ï½›E2｝有共同项，等同于A属于 {E2} 4度分隔为： {A2} ï½›E2｝有共同项  

【SN关系的更新】  å½“然，发现是一个核心问题，另外一个问题就是更新，因为SN的关系不会是一成不变的，在一个活跃的SN社区里，每天用户之间的关系的更新更是可观。这里只考虑关系添加的例子：  A: {A1} {A2}  E: {E1} {E2}  å½“A 与 E 直接建立了好友关系后，应该说整合系统的关系全都变化了，因为这个新的关系一定会导致一些关系的短路，从而导致很多现有的关系的调整。但是因为我们只存储2度分隔以内的关系，也只关心两度分隔以内的关系，因此当发生了一个新的关系后，2度内关系的变化一定是Aå’ŒE本身或者他们的一度关系的用户，再远的用户将不受这个关系的影响。  å› æ­¤é¦–å…ˆ 所有｛A1｝的元素的二度分隔集合里要加上E，所有｛E1｝的元素的二度分隔集合里要加上A。  ç„¶åŽæ˜¯äºŒåº¦çš„修正。分别加上对方的1度。 {A2} = {A2 + E1} {E2} = {E2 + A1}  æœ€åŽæ˜¯ä¸€åº¦çš„修正：A, E çš„ 一度{A1}{E1}需要加入E,A: {A1} = {A1 + E} {E1} = {E1 + A}