6.4 六度空间

1. 六度空间（Six Degrees of Separation）

2. 算法思路

//**********六度空间搜索函数**********
void SDS()
{
    for( each V in G )
    {
        count = BFS(V);
        Output(count/N);
    }
}

//**********原始BFS函数**********
void BFS( Vertex V)
{
    visited[V] = true;
    Enqueue(V, Q);
    while( !IsEmpty(Q) )
    {
        V = Dequeue(Q);
        for ( V 的每个邻接点 W )
        {
            if( !visited[W] )
            {
                visited[W] = true;
                Enqueue(W, Q);
            }
        }
    }
}

//**********修改的BFS函数**********
int BFS( Vertex V)              // 返回值改为int型，返回的是count
{
    visited[V] = true;
    count = 1;                  // count:记录访问结点的个数
    level = 0;                  // level:当前结点的层数
    last = V;                   // last:当前层访问的的最后一个结点
    Enqueue(V, Q);
    while( !IsEmpty(Q) )
    {
        V = Dequeue(Q);
        for ( V 的每个邻接点 W )
        {
            if( !visited[W] )
            {
                visited[W] = true;
                count++;
                Enqueue(W, Q);
                tail = W;       // tail:下一层的最后一个结点
            }
            if( V == last )     // 当弹出的结点V是last(最后一个结点)
            {
                level++;        // 更新level
                last = tail;    // 更新last，即将last指向tail
            }
            if( level == 6 )    // 当层数为6时，跳出循环
            {
                break;
            }   
        }
    }
    return count;
}