厦门网站模板,重庆网站推广联系方式,新媒体做图网站,wordpress模板游戏推广7-7 六度空间 (30 分)
一#xff1a;题目#xff1a;
六度空间”理论又称作“六度分隔#xff08;Six Degrees of Separation#xff09;”理论。这个理论可以通俗地阐述为#xff1a;“你和任何一个陌生人之间所间隔的人不会超过六个#xff0c;也就是说#xff0c;最…7-7 六度空间 (30 分)
一题目
六度空间”理论又称作“六度分隔Six Degrees of Separation”理论。这个理论可以通俗地阐述为“你和任何一个陌生人之间所间隔的人不会超过六个也就是说最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图 “六度空间”理论虽然得到广泛的认同并且正在得到越来越多的应用。但是数十年来试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式: 输入第1行给出两个正整数分别表示社交网络图的结点数N1N≤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%
二思路解析
用BFS遍历点时其实也就是层序遍历 这里的deep是记录层数的 由题目得知 最大层数不得超过六层 而在设计层数时 是将每次入队的邻接点全部出队 代表一层遍历结束然后记录邻接点的个数 即是可以到达目标结点的结点个数
三上码邻接矩阵存储数据 //不用考虑与目标点的距离小于6的多条路径问题因为已经记录下 这个结点了。当大于6时 也就是当递归结束时 将 返回 上一个结点 访问其未访问过的 记录
//路径权值相加 小于 6 的结点个数 同时 也就是 到达目标结点路径长度小于六的 的结点 总数
// dfs 当中的递归次数 也就是 到达目标结点的路径长度 小于六的结点次数
#includebits/stdc.h
using namespace std;//int visited[1001] {0};
int N,M;
int cnt;
typedef struct GNode* Ptrgraph;
typedef struct GNode{int Nv;int Ne;int Data[10001][10001];
}gnode;//创建图(用临界矩阵来表示)
void CreateGraph( Ptrgraph G)
{cin N M;G-Nv N;G-Ne M;for(int i 1; i G-Nv; i){for(int j 1; j G-Nv; j){G-Data[i][j] 0;}}for( int k 0; k G-Ne; k){int i,j;cin i j;G-Data[i][j] 1;G-Data[j][i] 1;}
}//BFS遍历
void BFS_Graph(Ptrgraph G,int a,int visited[]){int Queue[1001];int head 0,last 0;Queue[last] a;visited[a] 1;cnt;for(int deep 0; deep 6; deep) //deep表示层数 {vectorintv; while(head - last) //将每次入队的元素全部出队 也就是代表这一层的邻接点访问完了准备从 { //的deep 0 向deep靠近 int temp Queue[head];v.push_back(temp); }for(int i 0; i v.size(); i){ int temp2 v[i]; for(int i 1; i G-Nv; i){ if( visited[i] ! 1 G-Data[temp2][i] 1){ Queue[last] i;cnt;// 统计每个可以到达 目标结点的邻接点个数 visited[i] 1;} } } }
} int main(){Ptrgraph G;G (Ptrgraph)malloc(sizeof(struct GNode));CreateGraph(G);for(int i 1; i N; i ){ int visited[1001] {0};cnt 0;BFS_Graph(G,i,visited);double temp3 (double)cnt * 100.00/ N;printf(%d: %0.2f%%\n,i,temp3);}}
四DFS遍历最后一个点过不去
自己做的时候先用的是DFS遍历也就是一个递归 在形参上添加了一个记录路径长度的sum ,在设置递归失败条件上选择 sum6; 说的是容易 但自己在用递归的时候 不知走了多少弯路尤其在设置递归失败条件上 而且递归及其难理解本题当中的因为当遍历到邻接点都被访问过了便就返回上一层 所以要将所记录的路径长度 也要对应返回因此要将sum设置在形参上这样便可以将路径长度也返回。还有一个点因为是要输出多个点所以初始化的时候要将visited这个数组放到for循环里头。用DFS过不去原因我是从网上看的讲的是因为当遍历的最后一个点返回到初始点时 还有一条可以直达最后一个点的路径但因为已经标记过了所以便不在访问我不懂 大家可以再看看 可以打评论即便这道题没过但我又对递归又有了更深的认识重要的是自己学习的过程加油陌生人。
//不用考虑与目标点的距离小于6的多条路径问题因为已经记录下 这个结点了。当大于6时 也就是当递归结束时 将 返回 上一个结点 访问其未访问过的 记录
//路径权值相加 小于 6 的结点个数 同时 也就是 到达目标结点路径长度小于六的 的结点 总数
// dfs 当中的递归次数 也就是 到达目标结点的路径长度 小于六的结点次数
#includebits/stdc.h
using namespace std;//int visited[1001] {0};
int N,M;
int cnt;
typedef struct GNode* Ptrgraph;
typedef struct GNode{int Nv;int Ne;int Data[10001][10001];
}gnode;//创建图(用临界矩阵来表示)
void CreateGraph( Ptrgraph G){cin N M;G-Nv N;G-Ne M;for(int i 1; i G-Nv; i){for(int j 1; j G-Nv; j){G-Data[i][j] 0;}}for( int k 0; k G-Ne; k){int i,j;cin i j;G-Data[i][j] 1;G-Data[j][i] 1;}
}//DFS遍历
// 遇到递归失败条件后 依次返回到 上一层 对应的 a 和sum2;
void DFS_Graph(Ptrgraph G,int a,int sum2,int visited[]){ // sum2表示路径长度 if(sum2 6){return ;}cnt;//每一次递归就是一个可以到达目标结点的距离小于6的结点visited[a] 1;for(int j 1 ; j G-Nv; j){if( visited[j] ! 1 G-Data[a][j] ! 0){//sum2 G-Data[a][j]; //记录路径长度小于6的//cout sum2 endl;DFS_Graph( G,j,sum21,visited); }}}
int main(){Ptrgraph G;G (Ptrgraph)malloc(sizeof(struct GNode));CreateGraph(G);for(int i 1; i N; i){int visited[10001] {0};cnt 0;int sum1 0;//表示路径长度DFS_Graph(G,i,sum1,visited);//cout -----endl;// cout ::count endl;double temp (double)cnt*100.00 / N;printf(%d: %0.2f%%\n,i,temp);//visited[10001] {0};}}
