图 - 六度空间

题目

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> G[10010];
vector<bool> visit;
int cnt;

void bfs(int x)
{
	queue<int> Q;
	Q.push(x);
	int pos = x;
	int dis = 0;
	int temp;
	while (!Q.empty())
	{
		int cur = Q.front();
		Q.pop();
		for (int i = 0; i < G[cur].size(); i++)
		{
			if (!visit[G[cur][i]]) {
				visit[G[cur][i]] = true;
				Q.push(G[cur][i]);
				cnt++;
				temp = G[cur][i];  //更新该层的最后一个
			}
		}
		if (cur == pos){
			pos = temp;   //用temp 因为前一个pos可能没有扩展
			++dis;
			if (dis == 6) break;
		}
	}
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	visit.resize(n + 2);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		visit.assign(n+2, false);
		cnt = 0;
		if (!visit[i]){
			visit[i] = true;   //这两句可以放到bfs
			cnt++;
			bfs(i);
		}
		printf("%d: %.2f%%\n", i, (100.0*cnt / n));
	}
	return 0;
}

注：

• 用DFS要考虑到当一个点被判为距离为6时，它就返回了
• 并且该点已被标记访问过，它再也不能访问，也就是它连接的后面的点不能访问到
• 但其实有可能其他路径可以通过该点(到该点的距离不为6)访问到后面的点
• 该点被标记了，这种可能性就被丢失了

---

• BFS用在范围性扩展的问题上比较好
• 不断地向外扩展，不会丢失可能性