浙大数据结构：06-图3 六度空间

数据结构MOOC

PTA习题

这道题一开始用dfs做得，发现测试点4过不去。经查证，是dfs需要剪枝和优化才行，如果暴力会超时，所以采用bfs来做。调了半天，最后参考了一下再修改才过的。

1、条件准备

n,m分别存储结点数和边数，num存一次遍历能找到多少点。

d用来输出的，graph是邻接矩阵

#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;int n, m;
int num;
int visit[1005];
double d = 100.0;
bool graph[1005][1005];

先输入数据，建图。

然后循环遍历每个结点，bfs遍历，按格式输出。

int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin >> n >> m;for (int i = 0; i < m; i++){int a, b;cin >> a >> b;graph[a][b] = 1;graph[b][a] = 1;}for (int i = 1; i <= n; i++){memset(visit, 0, sizeof(visit));num = 0;bfs(i);cout << i << ": " << fixed << setprecision(2) << d * num / n << "%" << endl;}return 0;
}

2、bfs函数

还是用数组模拟队列，把起始结点放入，visit置1，num++.

level是当前已找完的层数，最多6层。

队列不为空并且，没到6层进栈，循环遍历，如果没走过且有路就放入队列中。

找完如果当前结点为上一层的最后一个结点，则更新层数和last

void bfs(int head)
{int q[1005]; int hh = 0, tt = -1;q[++tt] = head;visit[head] = 1;num++;int level = 0;int last = head;while (hh <= tt && level < 6){int cur = q[hh++];for (int i = 1; i <= n; i++){if (!visit[i] && graph[cur][i]){q[++tt] = i;num++;visit[i] = 1;}}if (cur == last){last = q[tt];level++;}}
}

3、总结

这道题我一开始觉得挺简单的，但总是测试点4过不去，调试了老半天，还是有点坑的。

完整代码如下：

#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;int n, m;
int num;
int visit[1005];
double d = 100.0;
bool graph[1005][1005];void bfs(int head)
{int q[1005]; int hh = 0, tt = -1;q[++tt] = head;visit[head] = 1;num++;int level = 0;int last = head;while (hh <= tt && level < 6){int cur = q[hh++];for (int i = 1; i <= n; i++){if (!visit[i] && graph[cur][i]){q[++tt] = i;num++;visit[i] = 1;}}if (cur == last){last = q[tt];level++;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin >> n >> m;for (int i = 0; i < m; i++){int a, b;cin >> a >> b;graph[a][b] = 1;graph[b][a] = 1;}for (int i = 1; i <= n; i++){memset(visit, 0, sizeof(visit));num = 0;bfs(i);cout << i << ": " << fixed << setprecision(2) << d * num / n << "%" << endl;}return 0;
}