06-图3 六度空间
程序员文章站
2024-01-17 18:15:40
...
“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103,表示人数)、边数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%
总结
需要注意的地方:
- 最后需要输出百分制,所以要注意int类型会取整
- 每遍历一个结点,需要重置标记
- 循环退出的时间
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxVertexNum 10001
typedef int Vertex;
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex Adjv; /* 邻接点下标 */
PtrToAdjVNode Next;/* 指向下一个邻接点的指针 */
};
/* 顶点表头结点的定义 */
typedef struct Vnode{
PtrToAdjVNode FirstEdge;/* 边表头指针 */
} AdjList[MaxVertexNum]; /* AdjList是邻接表类型 */
/* 图结点的定义 */
typedef struct GNode *LGraph;
struct GNode{
int Ne; /*顶点*/
int Nv; /*边数*/
AdjList G; /*邻接表*/
};
/*建邻接表*/
LGraph BuilGraph(int N,int M){
Vertex V1,V2;
PtrToAdjVNode Temp;
//创建一个图
LGraph Graph=(LGraph)malloc(sizeof(struct GNode));
Graph->Ne=N;
Graph->Nv=M;
for (int i = 0; i <=N; i++)
Graph->G[i].FirstEdge=NULL;
//输入一个图
for (int i = 0; i < M; i++)
{
scanf("%d %d",&V1,&V2);
/* 为V1建立新的邻接点 */
Temp=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
Temp->Adjv=V2;
Temp->Next=Graph->G[V1].FirstEdge;
Graph->G[V1].FirstEdge=Temp;
/* 为V2建立新的邻接点 */
Temp=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
Temp->Adjv=V1;
Temp->Next=Graph->G[V2].FirstEdge;
Graph->G[V2].FirstEdge=Temp;
}
return Graph;
}
/*标记是否被遍历*/
int Visited[MaxVertexNum]={0};
/*计算结点数*/
float BFS(LGraph Graph,Vertex V){
float Count;
Vertex Level=0,Last=V,Tail;
PtrToAdjVNode Temp;
Vertex Q[MaxVertexNum];/*队列*/
int Front=0,Rear=0;
Visited[V]=1,Count=1;
/*入队*/
Rear=(Rear+1)%MaxVertexNum;
Q[Rear]=V;
/*计算结点数*/
while (Front!=Rear)
{
/*出队*/
Front=(Front+1)%MaxVertexNum;
V=Q[Front];
Temp=Graph->G[V].FirstEdge;
while (Temp)
{
if (!Visited[Temp->Adjv])/*没有被遍历过*/
{
Rear=(Rear+1)%MaxVertexNum;
Q[Rear]=Temp->Adjv;
Visited[Temp->Adjv]=1;
Tail=Temp->Adjv;
Count+=1;
}
Temp=Temp->Next;
}
/*遍历完一层以后,层数增加*/
if (Last==V){
Last=Tail;
Level++;
}
/*遍历完六层,退出*/
if (Level==6) break;
}
return Count;
}
void SDS(LGraph Graph,int N){
Vertex V;
float Count;
for ( V = 1; V <= N; V++)
{
Count=BFS(Graph,V);
printf("%d: %.2f%%\n",V,(Count/N)*100);
/*对标记进行重置*/
memset(Visited,0,sizeof(Visited));
}
}
int main()
{
LGraph Graph;
int N,M;
scanf("%d %d",&N,&M);
Graph=BuilGraph(N,M);
SDS(Graph,N);
return 0;
}