浙大数据结构：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;
}