题目

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

讯享网
图1 六度空间示意图

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

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

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10​4​​，表示人数）、边数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> using namespace std; #define MaxVertexNum 10000//最多顶点（结点）数 #define MaxDistance 6//BFS广度优先搜索允许遍历到的层数 #define DefaultWeight 1//无边的权重要求，则默认为1 #define QERROR 0//队列发生错误 typedef int Vertex;//用顶点下标表示顶点 typedef int WeightType;//边的权重 //定义图的边 typedef struct ENode *PtrToENode; struct ENode{ Vertex V1, V2; //有向边<V1,V2> WeightType Weight;//权重 }; typedef PtrToENode Edge; //邻接点的定义 typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; //邻接点的下标 WeightType Weight;//边权重 PtrToAdjVNode Next;//指向下一个邻接点的指针 }; //顶点表头的定义 typedef struct Vnode{ PtrToAdjVNode FirstEdge;//变表头指针 } AdjList[MaxVertexNum];//AdjList是邻接表类型 //图结点的定义 typedef struct GNode *PtrToGNode; struct GNode{ int Nv;//顶点数 int Ne;//边数 bool *visited;//顶点被访问状态数组的指针 AdjList G;//邻接表 }; typedef PtrToGNode LGraph;//以邻接表方式存储的图类型 //队列的结点定义 typedef struct Node *PtrToNode; struct Node{ Vertex Data;//队列结点存储的数据 PtrToNode Next;//指向下一个队列结点的指针 }; typedef PtrToNode Position; //队列的定义 struct QNode{ Position Front, Rear;//队列的头结点和尾结点 int MaxSize;//队列的最大可存储大小 }; typedef struct QNode *Queue;//以链表的形式实现队列 LGraph CreateGraph(int Nv); void InsertEdge(LGraph Graph, Edge E); void BFSToSix(LGraph Graph); int BFS(LGraph Graph, Vertex v); Queue CreateQueue(int MaxSize); bool QIsEmpty(Queue Q); Vertex DeleteQ(Queue Q); void AddQ(Queue Q, Vertex v); int main() { /* //测试用例 int N; int M; N = 10; LGraph Graph; Graph = CreateGraph(N); M = 9; int V1Arr[M] = {1,2,3,4,5,6,7,8,9}; int V2Arr[M] = {2,3,4,5,6,7,8,9,10}; Edge E; E = new ENode; for(int e=0; e<M; e++){ E->V1 = V1Arr[e]; E->V2 = V2Arr[e]; E->Weight = DefaultWeight; InsertEdge(Graph, E); } BFSToSix(Graph); */ //正式应用 int N, M; LGraph Graph; Edge E; cin >> N; //输入结点总数 Graph = CreateGraph(N); //创建无边图 cin >> M; //输入边的个数 E = new ENode; for(int i=0; i<M; i++){ cin >> E->V1; cin >> E->V2; E->Weight = DefaultWeight; InsertEdge(Graph, E); } BFSToSix(Graph);//六度分隔理论模拟 return 0; } void BFSToSix(LGraph Graph) { int SixVertexNum; float percent; if(Graph->Nv != 0){ for(Vertex v=1; v<Graph->Nv; v++){ //在六步内可遍历到的顶点数（其中还要加上结点本身） SixVertexNum = BFS(Graph, v) +1; //在六步内可遍历到的顶点数占总结点数的百分比（结点从1开始，需要减去0这个无用结点） percent = float(SixVertexNum)/float(Graph->Nv-1); printf("%d: %.2f%\n", v, percent*100); //清空结点被遍历状态 for(int i=0; i<Graph->Nv; i++) Graph->visited[i] = false; } } } int BFS(LGraph Graph, Vertex v) { PtrToAdjVNode w; int D = 0; int SixVertexNum = 0; Queue Q; Q = CreateQueue(MaxVertexNum);//创建队列 Graph->visited[v] = true; AddQ(Q, v); AddQ(Q, 0);//插入队列中的0，用于表示新的一层的开始 ++D;//所在的层数 while(!QIsEmpty(Q)){ v = DeleteQ(Q); if(v == 0 && D >= MaxDistance) break; //表示层数已超过6 if(v == 0 && D < MaxDistance){//层数还未超过6 AddQ(Q, 0); ++D; continue; } for(w=Graph->G[v].FirstEdge; w != NULL; w=w->Next){ if(!Graph->visited[w->AdjV]){ Graph->visited[w->AdjV] = true; AddQ(Q, w->AdjV); ++SixVertexNum; } } } return SixVertexNum; } void InsertEdge(LGraph Graph, Edge E) { PtrToAdjVNode NewNode; ++Graph->Ne; //插入<V1,V2> NewNode = new AdjVNode; NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; //插入<V2,V1> NewNode = new AdjVNode; NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode; } LGraph CreateGraph(int N) { LGraph Graph; Graph = new GNode; Graph->Nv = N+1; //结点从1开始 Graph->Ne = 0; Graph->visited = new bool [N+1]; for(int i=1; i<Graph->Nv; i++) Graph->visited[i] = false; for(int v=1; v<Graph->Nv; v++) Graph->G[v].FirstEdge = NULL; return Graph; } Queue CreateQueue(int MaxSize) { Queue Q; Q = new QNode; Q->Front = Q->Rear = NULL; Q->MaxSize = MaxSize; return Q; } bool QIsEmpty(Queue Q) { return (Q->Front == NULL); } void AddQ(Queue Q, Vertex v) { Position NewNode; NewNode = new Node; NewNode->Data = v; NewNode->Next = NULL; if(QIsEmpty(Q)){ Q->Front = NewNode; Q->Rear = NewNode; } else{ Q->Rear->Next = NewNode; Q->Rear = NewNode; } } Vertex DeleteQ(Queue Q) { Position FrontNode; Vertex FrontData; if( QIsEmpty(Q)){ return QERROR; } else{ FrontNode = Q->Front; if( Q->Front == Q->Rear) Q->Front = Q->Rear = NULL; else Q->Front = Q->Front->Next; FrontData = FrontNode->Data; delete FrontNode; return FrontData; } }