C++公交站点

一、题目要求

1、编程实现

一个无向图表示的公交线路，给定 n 个站点，m 条边，站点编号为 1 到 n，请输出 1 号站点分别到 2、3、4......n 站点至少需要经过几个站。

2、输入输出

输入描述：第一行两个整数 n(5≤n≤180)和 m(1≤m≤4958)，分别表示站点数和边数，整数之间以一个空格隔开。
后面 m 行，每行两个数 ui和 vi，表示 ui和 vi(1≤ui，vi≤n，ui≠vi)之间有一条无向边ui和 vi 可直接到达，整数之间以一个空格隔开。数据保证无重复站点，类似1 2和2 1视为重复站点。

输出描述：一行，包含 n-1 个整数，分别表示站点1到 2、3、4...·n 站点至少需要几个站不能到达该站点时，使用 0 表示，整数之间以一个空格隔开。

输入样例：

5 6
1 2
1 3
2 4
3 4
3 5
4 5

输出样例：

1 1 2 2

二、算法分析

1. 从给定题目的初步分析可以看出，这是一个比较典型的图论问题
2. 这个题目解法有很多种，可以使用邻接矩阵或者邻接图，结合DFS或者BFS或者DP都可以
3. 我们这边今天就采用邻接表加广度优先搜索算法BFS实现
4. 在确定使用BFS+ADJ算法之后需要事先定义好一个动态数组，用来实现邻接表
5. 同时需要设计一个hashtable用来作为每个站点访问的标记，还需要一个数组用来存放每个站点经过的站点数
6. 然后BFS的实现其实可以使用队列queue来实现比较方便，队列的实现关键就在于入队、出队以及是否队空操作
7. 整个程序可以分成三个部分：第一部分数据的初始化，包括各种变量数组的定义以及邻接表的初始化
8. 第二部分就是bfs的实现，从站点1开始逐一入队，出队，搜索相邻的站点，保存相应经过站点数等
9. 第三部分就是输出保存经过站点数组里面的每一个值

三、程序编写

#include<bits/stdc++.h>
using namespace std;
const int N = 185;
int visited[N],a[N];//visited已经访问过
vector<int> grid[N];//邻接表存放相邻的点
int n,m;  //n行  m条边，x、y为顶点，z为它们的距离
void bfs();


int main()
{
  cin >> n >> m;
  for(int i=1;i<=m;i++)
  {
    int x,y;
    //输入每条边及对应的距离
    cin >> x >> y;
    grid[x].push_back(y);
    grid[y].push_back(x);
  }
  
  bfs();
  for(int i=2;i<=n;i++)
  {
    cout << a[i] << ' ';
  }
  return 0;
}


void bfs()
{
  visited[1] = 1;
  queue<int> q;
  q.push(1);
  while(!q.empty())
  {
    int u = q.front();
    q.pop();
    for(int i=0;i<grid[u].size();i++)
    {
      int v = grid[u][i];
      if(!visited[v])
      {
        visited[v] = 1;
        a[v] = a[u] + 1;
        q.push(v);
      }
    }    
  }
}

本文作者：小兔子编程 作者首页：小兔子编程-CSDN博客

四、运行结果

5 6
1 2
1 3
2 4
3 4
3 5
4 5


1 1 2 2

五、考点分析

难度级别：中等，这题相对而言在于图的存储形式和遍历方式的理解，具体主要考查如下：

1. 分析题目，找到解题思路
2. 充分掌握变量和数组的定义和使用
3. 学会动态动态数组vector的原理和使用
4. 学会邻接表的存储形式和实现原理
5. 学会BFS的原理和实现方式
6. 学会队列的原理和使用方法
7. 学会队列的操作方式：入队、出队、队空判定等
8. 学会hashtable的使用方法
9. 学会输入流对象cin的使用，从键盘读入相应的数据
10. 学会for循环的使用，在确定循环次数的时候推荐使用学会
11. 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
12. 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
13. 充分掌握变量定义和使用、循环语句、vector、队列和BFS算法的应用