7-36 社交网络图中结点的“重要性”计算
问题描述来自PTA-数据结构与算法题目集（中文）7-36 社交网络图中结点的“重要性”计算 ：
在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。
“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中，结点vi 的“紧密度中心性”Cc(vi) )数学上定义为vi 到其余所有结点vj (j≠i) 的最短距离d(vi,vj)的平均值的倒数：
对于非连通图，所有结点的紧密度中心性都是0。
给定一个无权的无向图以及其中的一组结点，计算这组结点中每个结点的紧密度中心性。
输入格式:
输入第一行给出两个正整数N和M，其中N(≤104)是图中结点个数，顺便假设结点从1到N编号；M（≤ 105）是边的条数。随后的M行中，每行给出一条边的信息，即该边连接的两个结点编号，中间用空格分隔。最后一行给出需要计算紧密度中心性的这组结点的个数K（≤100）以及K个结点编号，用空格分隔。
输出格式:
按照Cc(i)=x.xx的格式输出K个给定结点的紧密度中心性，每个输出占一行，结果保留到小数点后2位。
输入样例:
9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9
输出样例:
Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35
Author: DS课程组
Organization: 浙江大学
Time Limit: 20000 ms
Memory Limit: 64 MB
Code Size Limit: 16 KB
博客中主要为思路与算法思想，完整的代码参看我的github
思路分析
求最短路径,涉及多个点，一开始想要用floyd等算法，但是其复杂度为O(N3)，对于104个点来说过一定会爆炸，dijikstra不适合
考虑到节点的边权重都为1,求到各个节点的最短路径可以简化为对图进行宽度优先遍历(BFS),第一轮遍历到的距离dis(1)为1,第j轮遍历到的dis(j)=dis(j1)+1
那么对每个节点求紧密度中心性的复杂度就为O(N)，时间应该可以
宽度优先遍历
太久没写宽度优先便利了，代码不是很规范
宽度优先遍历就是从一节点开始，访问与其相临接的所有节点，再继续访问临接节点的临接节点，一层一层访问，可以采用队列实现
double BFS(int start,int node){
for(int i = 1;i < MAXN;i++)
{
visited[i] = false;
}
queue<int> bfsqueue;
int dis[node+1];int visit = 0;
double sumdis = 0.0;
visited[start] = true;
for(int i = 1;i <= node;i++){
if(graph[start][i] == true && visited[i] == false){
bfsqueue.push(i);
dis[i] = 1;
sumdis += dis[i];
visit++;
visited[i] = true;
}
}
while(bfsqueue.size()>0){
int cur = bfsqueue.front();
bfsqueue.pop();
for(int i = 1;i <= node;i++){
if(graph[cur][i]== true && visited[i]==false){
bfsqueue.push(i);
dis[i] = dis[cur]+1;
sumdis += dis[i];
visit++;
visited[i] = true;
}
}
}
double result = (double) (node - 1)/sumdis;
if(visit != node - 1) return 0;
else return result;
}
注意MLE:MEMORY LIMIT EXCEEDED
遇到了MLE，看 没想好叫什么名字-5-36 社交网络图中结点的“重要性”计算 (30分)使用int二维数组存储图，我使用bool二维数组，讲道理应该不会MLE
感谢 team39-Memory Limit Exceeded（内存超限）中的讲解，不要一次性清零，只对要用的节点清零，更改后就Accepted | 
转播
