····挑战算法 ，高手请进·····

Question

····挑战算法 ，高手请进·····friendrelatinshopF_id int(11) auto_increment 自动编号F_username varchar(50)      用户名F_friend varchar(50)        用户名 For Example
f_id        F_username           f_friend
------------------------------------------------------
1           a                    b
2           a                    c
3           a                    d
4           f                    a
5           e                    f
6           g                    a
7           h                    f
8           b                    c
9           i                    k
10          b                    g
11          c                    d
12          d                    g
.....                   
要求：
---------------------------------------------
得到任意2个人的所有关系路径 因为 a->b   (line 1) b->g   (line 10) g->a   (line 5)所以：a和g 的关系路径是: a->b->g
又因为: a->c   (line 2) c->d   (line 11) d->g   (line 12)

所以：a和g的关系还有 : a->c->d->g用最简单的算法 求 a和 g 所以的关系路径。
又比如：因为：a->bb->gg->jj->k所以：
a->b->g->j->k
Function friendrelatinshop(friend1,friend2) if friend1 与 friend2 有关系 then

friendrelatinshop = "a -> ? -> ···· -> k；a->?->****->k"
else

friendrelatinshop = "没有关系"
end ifend function这个算法好像好复杂哦，看看谁的算法最快？

Answer 1

1.我个人认为数据库设计不合理，f_friend应该为id
2.下面的代码我写了一个简单的思路，为了考虑速度用了数组(1024应该可以了）
还有一些代码没有写完，剩下的部分应该不难了
int GetNextFrend(int f,int id)
{
   //use the top 1 select a frend while f_friend>id
   // no user return -1
}#define MAX_PRE 1024
int frendArray[MAX_PRE];
int frendNum=0;
bool NoFind = true;
bool HaveThisFrend(int b,int num)
{
   //看frendArray[MAX_PRE]是否有b
  //num为已经加的用户
}void HaveRela(int a,int b,int num)
{
  if(num>=MAX_PRE) return;
  int nID=1; 
  int fNext = GetNextFrend(a,1);
  while(NoFind&&fNext!=-1)
  {
if(HaveThisFrend(fNext,num))
          break;
        else
        {
  if(fNext ==b)
  {
frendNum = num+1;
NoFind = false;
  }
          else
          {
frendArray[num]=fNext;
HaveRela(fNext,b,num+1);
  }
}  }  
}
main()
{
   //判断1和3有没有relation
   HaveRal(1,3,0);
   if(!NOFind)
    {
      //打印
    }
}

Answer 2

一个最基本undirected graph。
帮你找一个C#写的代码

Answer 3

上面HaveRela应该是
void HaveRela(int a,int b,int num)
{
  if(num>=MAX_PRE) return;
  int nID=1; 
  int fNext = GetNextFrend(a,1);
  while(NoFind&&fNext!=-1)
  {
if(HaveThisFrend(fNext,num))
          continu;
        else
        {
  if(fNext ==b)
  {
frendNum = num+1;
NoFind = false;
  }
          else
          {
frendArray[num]=fNext;
HaveRela(fNext,b,num+1);
  }
}
        fNext = GetNextFrend(a,1fNext);
  }  
}

Answer 4

macbolo() 能简单说一下你的思路吗

Answer 5

大家一起研究一下   http://www.bashu.com.cn/olympic/bashu/graph.htm

Answer 6

用的递归
如果有a-g-c-b的问题可以分解为a-g,再寻找g-b的路径，这样一直搞下去就可以了。
递归过程中注意的问题
1。要遍寻和a有关系的所有人，我用的GetNextFrend(int f,int id)
   在数据库中查询要按 f_friend（我认为是int字段，表示的是朋友的id)升序排列,找出来
大于原来id的第一个朋友的id。这个sql语句应该很好写
2。避免死循环，已经挑选的朋友放到frendArray中
   bool HaveThisFrend(int b,int num)，是用来检验有没有已经加了这个人
   应为没有用到链表，速度会快很多，但需要注意的是HaveThisFrend的第二个参数是用来保证需要检验的人数
HaveRela这个函数还是有错，对不起，我看应该是这个
void HaveRela(int a,int b,int num)
{
  if(num>=MAX_PRE) return;
  int nID=1; 
  int fNext = GetNextFrend(a,1);
  while(NoFind&&fNext!=-1)
  {
if(HaveThisFrend(fNext,num))
         {
         }
        else
        {
  if(fNext ==b)
  {
frendNum = num+1;
NoFind = false;
  }
          else
          {
frendArray[num]=fNext;
HaveRela(fNext,b,num+1);
  }
}
         fNext = GetNextFrend(a,1fNext);
  }  
}
如果还有什么错误，希望大家指正