六度空间（Six Degrees of Separation）
- 你和任何一个陌生人之间所间隔的人不会超过六个
题目：给定社交网络图，请对每个节点计算符合“六度空间”理论的结点占结点总数的百分比
算法思路：
- 对每个节点，进行广度优先搜索
- 搜索过程中累计访问的节点数
- 需要记录“层”数，仅计算6层以内的节点数
具体过程：
对每一个结点求其6层以内可以访问的结点的总数，除以总数n就是该节点符合“六度空间”理论的结点占结点总数的百分比
变量level表示层数，last表示该层访问的最后一个结点，根节点入队列，last初始化为根节点，从队列中取元素，并将该元素相连的没有访问过的元素入队列，所有入栈的元素都要设置成已经访问过；当取出的元素等于last时，表示该层访问完了，层数加1，进入下一层，直到第六层访问完时，退出，返回入栈的元素总数。
void SDS()
{
for (each V in G)
{
count = BFS(V);
Output(count / N);
}
}
int BFS(Vertex V)
{
visited[V] = true; count = 1; //count统计6层内元素个数
level = 0; last = V; //last表示该层最后一个元素
Enqueue(V, Q);
while (!IsEmpty(Q))
{
V = Dequeue(Q);
for (V 的每个邻接点W)
if (!visited[W])
{
visited[W] = true;
Enqueue(W, Q); count++;
tail = W;
}
if (V == last){//取出结点等于该层最后一个结点，该层元素全部已经访问
level++; last = tail;
}
if (level == 6) break;
}
return count;
}
转载自原文链接, 如需删除请联系管理员。
原文链接：【图(上)】六度空间，转载请注明来源！