06-图3 六度空间 (30分)---AI那点小事

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

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

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

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数NN（1

#include <iostream> #include <stdio.h> #include <queue> using namespace std; class Graph { private: int Nv; //顶点数 int Ne; //边数 int** G; //邻接矩阵 int* isVisited; //访问数组 public: //构造函数 Graph(int nv,int ne) { this->Nv = nv; this->Ne = ne; this->isVisited = new int[nv]; this->G = new int*[nv]; for ( int i = 0 ; i < nv ; i++) { this->G[i] = new int[nv]; this->isVisited[i] = 0; } for ( int i = 0 ; i < nv ; i++){ for ( int j = 0 ; j < nv ; j++){ this->G[i][j] = 0; this->G[i][i] = 1; } } for ( int i = 0 ; i < this->Ne ; i++){ int a,b; cin>>a>>b; this->G[a-1][b-1] = 1; this->G[b-1][a-1] = 1; } } int BFS(int start) { queue<int> que; int cnt = 1; int level = 0; int last = start; int tail; this->isVisited[start] = 1; que.push(start); while(!que.empty()) { int neiborgh = que.front(); que.pop(); for ( int i = 0 ; i < this->Nv ; i++) { if ( this->G[neiborgh][i] && !this->isVisited[i]) { que.push(i); this->isVisited[i] = 1; cnt++; tail = i; } } if (neiborgh == last){ level++; last = tail; } if ( level == 6){ break; } } return cnt; } void SVD(){ for ( int i = 0 ; i < this->Nv ; i++ ){ MemSet_Visited(); int cnt = BFS(i); double percent = cnt * 1.0 / this->Nv; printf("%d: %.2f%%n",i+1,percent*100); } } void MemSet_Visited(){ for(int i = 0 ; i < this->Nv ; i++){ this->isVisited[i] = 0; } } }; int main() { int nv,ne; cin>>nv>>ne; Graph graph(nv,ne); graph.SVD(); return 0; }

---来自腾讯云社区的---AI那点小事