六度空间理论

描述

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入

多组数据，每组数据m+1行。第一行有两个数字n和m，代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b，代表这两个人互相认识。当n和m都等于0时，输入结束。

输出

多组数据，每组数据m+1行。第一行有两个数字n和m，代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b，代表这两个人互相认识。当n和m都等于0时，输入结束。

输入样例 1

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
9 10
0 0

输出样例 1

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
1: 70.00%
2: 80.00%
3: 80.00%
4: 80.00%
5: 80.00%
6: 80.00%
7: 80.00%
8: 70.00%
9: 20.00%
10: 20.00%

AC 代码

#include <iostream>
#include <cstdio>


using namespace std;

const int N = 100;

typedef struct
{
	int vexs[N];
	int arcs[N][N];
	int vexnum, arcnum;
}AMGraph;

void createUDN(AMGraph &g, int vexnum, int arcnum)			// 这里创建的是无向网
{
	g.vexnum = vexnum;
	g.arcnum = arcnum;

	for (int i = 1; i <= vexnum; i++)
		g.vexs[i] = i;

	for (int i = 1; i <= vexnum; i ++)
		for (int j = 1; j <= vexnum; j ++)
			g.arcs[i][j] = N;

	for (int i = 0; i < arcnum; i ++)
	{
		int v1, v2;
		cin >> v1 >> v2;
		g.arcs[v1][v2] = 1;									// 无向网的特性，对称和对角线为0
		g.arcs[v2][v1] = 1;
	}

	for (int i = 1; i <= arcnum; i++)
		g.arcs[i][i] = 0;
}

void shortPath_Dij(AMGraph g, int v1)
{
	bool s[N];												// 表示是否找到了最短路径
	int D[N];												// 表示该点到起点的距离
	for (int i = 1; i <= g.vexnum; i++)
	{
		s[i] = false;
		D[i] = g.arcs[v1][i];
	}

	s[v1] = true;
	D[v1] = 0;

	int min;
	int tmp;
	for (int v = 1; v < g.vexnum; v++)						// 寻求的次数
	{
		for (int i = 1; i <= g.vexnum; i++)
		{
			min = N;
			if (!s[i] && D[i] < min)
			{
				tmp = i; 
				min = D[i];
			}
		}

		s[tmp] = true;										// 注意将这个的状态置为true，表示找到了最短路径

		for (int i = 1; i <= g.vexnum; i++)
			if (!s[i] && (D[tmp] + g.arcs[tmp][i] < D[i]))
				D[i] = D[tmp] + g.arcs[tmp][i];
	}

	int cnt = 0;
	for (int i = 1; i <= g.vexnum; i++)
		if (D[i] <= 6)
			cnt++;

	double rate = ((double)cnt / g.vexnum) * 100;	// 数据处理和符号要小心
	printf("%d: %.2lf\%%\n",v1, rate);
}

int main()
{
	int n, m;
	while (cin >> n >> m, n && m)
	{
		AMGraph g;

		createDN(g, n, m);

		for (int i = 1; i <= n; i++)				// 进行遍历求最短路径
			shortPath_Dij(g, i);
	}

	return 0;
}

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

“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

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

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10 ​3​​ ，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出样例：

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

思路：

一开始用的深搜，就是不行，好像是链会被截断所以不行，就换了广搜，直接通过。

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1005][1005];
int n , m;
int book[1005] ,   ans , e[1005];
struct stu
{
       int kk;
       int s;//存储步数
}que[1005];
void bfs(int k)
{
    
    int head = 1 , tail = 1 , cur;
    que[tail].kk = k;
    book[k] = 1;
    que[tail].s = 0;
    ans++;//加上自己本身
    tail++;
    while(head < tail)
    {
        cur = que[head].kk;
        for(int i = 1 ; i <= n ; i++)
        {
            if(f[cur][i] == 1 && book[i] == 0)
            {
                book[i] = 1;
                que[tail].kk = i;
                que[tail].s = que[head].s + 1;//步数是父亲的步数加1
                if(que[tail].s <= 6)
                    ans++;
                else
                    break;
                tail++;
            }
        }
        head++;
    }
}
int main()
{
    cin>>n>>m;
    int x , y;
    for(int i = 1 ; i <= m ; i++)
    {
        cin>>x>>y;
        f[x][y] = 1;f[y][x] = 1;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        memset(book , 0 , sizeof(book));
        ans = 0;
        bfs(i);
        e[i] = ans;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        cout<<i<<": ";
        printf("%.2f" , e[i]*1.0 / n * 100);
        cout<<"%"<<endl;
    }
}

       在现实生活中，人际关系错综复杂，遇到难题，左右为难，致命问题保大保小、老妈还是老婆，这个是送命题，一般是不会出现，但是由于社会的发展，过年问题(孩子少，在哪里过年，另一方都会不热闹），这些困扰我们的问题，通过人与人的距离计算可以辅助我们做出选择。

　　六度空间理论-在理论情况下，你与任何人的距离不超过6，即通过自我关系网，每一环节达到关系网的极值，不会超过6。然而在现实中，这个理论只是纸上谈兵，例如我与某某名人，他们看都不会看我一眼，关系就等同我与路边的乞丐的关系，绝不是看不起乞丐。回到主题，距离，在学校，我们知道点与点的距离可以由公式得到，那么人与人的距离如何计算呢？有什么标准呢？人与人的距离可以解决人际关系吗？

　　以自己为例子，将朋友，同事，亲人划分三流九等，距离数据从1~5 ，其一为亲人初始为1，　其一为朋友初始为3，其一为其他人初始值为4，其他人包括同事、见过几面的陌生人，距离划分完成，每一个等级划分后，同等级也是有区别的，朋友有酒肉朋友，知心朋友等，等级划分完成，通过距离值得大小，即离中心的距离，决定着我们对人的态度，矛盾的时候的处理方法。有时候我也很困惑，明明距离是4甚至是5，却做着3才能做的事情，陌生人应该有陌生人的状态，在力所能及和不给他人带来麻烦的情况下，可以适当帮助。

　　距离也不是一成不变的，人与人的距离随着关系的相处，可以做加减法，随着距离的变迁，等级也会跨越，比如从陌生人到达朋友，再如亲人冷漠也会变为陌生人。