问题描述
假设有两条地铁线路，1 号线为直线线路，2 号线为环线线路，假设 1 号线的各个站点名称分别为 “A” “B” “C” “D” “E”“F” “G” "H"2号线的各个站点名称分别为"C" “I” “J” “K” “F” “L” “M” “N”;另外，假设地铁都是双向运行的。 现给出两个地铁站名分别作为起点和终点，请给出从起点到终点至少需要多少站。
解题思路回顾一下题目需要我们做什么：现给出两个地铁站名分别作为起点和终点，请给出从起点到终点至少需要多少站。如果将地铁线路图看为一个无向图，那么解决此问题就变得尤为简单。对于一个无向图，我们很容易能想到的就是深度优先搜索DFS以及广度优先搜索BFS，而本题我们要求解的是从某点经过最少的点到达另一点，这里推荐使用广度优先搜索，为什么不是DFS呢？其实两种方式都可以求解此问题，只是出发点不同罢了，DFS是一条路走到黑，不撞南墙不回头，每一次都能得到解，但这个解是不是最优解还有待比较，这里的比较就涉及到记录每一次前进记录当前已经前进的步数，这样能在后续遍历时进行一定程度的剪枝（当当前解超过最优解时不再深入搜索），显然记录状态是比较麻烦的。那么广度优先搜索有什么好处？层次递进，BFS类似于二叉树中的层次遍历（二叉搜索树(BST)创建以及层次、先、中、后序遍历），搜索时是逐层推进，那么如果出现一种解决方案，那么我们就已经找到了最优解。如果我们只是需要找到一种解决方案，那么不需要记录当前节点的步数状态，最先得到的解一定是最优解。BFS广度优先搜索对于每一个站点，直接使用站名是不方便的，我们对每一个站点编号A ~ N 编号为 0 ~ 13 共14站在数据结构课程中学到过这个方法，搜索之前必要的事情就是采用一种手段去表示地铁线路图。这里使用邻接矩阵来表示每一个站点与其他站点的连通关系。邻接矩阵表示为：具体做法：创建14 x 14的二维数组初始化为0，站点间直接连通则将值修改为1；对于地铁线路，使用结构体edge表示前后站的关系（用于后续查找最短路线，类似于双向链表）struct edge {//路线
int startSta;//起始站点编号
int endSta;//下一站站点编号
edge(int sS, int eS) :startSta(sS), endSta(eS) {}//构造函数
};
edge结构体包含两部分：startSta 表示起始站点编号，endSta 表示下一站站点编号，另外重载了构造函数方便后续使用。需要注意的是：广度优先搜索时注意不能加入之前已经加入过的节点或边，我们需要在访问某节点后将该节点标记，下一次搜索到的时候不再加入队列，这样确保了是逐层推进，不会出现故技重施、梅开二度的现象。代码含有大量注释，可放心食用（手动滑稽）头文件（地铁路线问题.h）#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
using namespace std;
#define STATIONNUMS 14 //地铁站的数量
int sstation = 1; //起始站的位置
int estation = 11; //终点站位置
struct edge {//路线
int startSta;//起始站点编号
int endSta;//下一站站点编号
edge(int sS, int eS) :startSta(sS), endSta(eS) {}//构造函数
};
queue<edge> que;//用于bfs的队列
unordered_set<int> visitedSta;//已将访问过的站点，不再重复加入
vector<char> stations{ 'A','B','C','D','E','F','G','H','I','J','K','L','M','N' };//站的具体名称
vector<vector<int>> staInf(STATIONNUMS, vector<int>(STATIONNUMS, 0));//初始化二维数组值设置为-1
vector<edge> path;//记录走过的站点
vector<int> ans;//最终结果
void initStaInf(vector<edge>& stas);//初始化邻接矩阵
void printMatrix();//打印邻接矩阵
void bfs(const char& startSta, const char& endSta);//广度优先遍历
源文件（地铁路线问题.cpp）#include "地铁路线问题.h"
void initStaInf(vector<edge>& stas) {
for (auto& p : stas) {
//标记两站之间可以互通 直接相连
staInf[p.startSta][p.endSta] = staInf[p.endSta][p.startSta] = 1;
}
}
void printMatrix() {
cout << "地铁路线图可用邻接矩阵表示为:"<<endl<< "
";
for (int i = 0; i < stations.size(); i++) {
cout << stations[i] << " ";
}cout << endl;
for (int i = 0; i < staInf.size(); i++) {
cout << stations[i] << " ";
for (int j = 0; j < staInf[i].size(); j++) {
if (staInf[i][j])
cout << "●";
else cout << "○";
}cout << endl;
}
}
void bfs() {
que.push(edge(-1, sstation));//始发站边加入
visitedSta.insert(sstation);
while (!(que.empty())) {//队列不为空
edge e = que.front();
que.pop();
int curSta = e.endSta;//当前站点
//visitedSta.insert(curSta);//加入集合，防止重复加入
path.push_back(e);//访问过的边加入到路径数组中
for (int j = 0; j < STATIONNUMS; j++) {
int staStatus = staInf[curSta][j];//该站的状态
if (staStatus && (visitedSta.find(j) == visitedSta.end())) {//可以到达这一站且此之前没访问过
edge newE(curSta, j);
que.push(newE);
visitedSta.insert(j);
if (j == estation) {
path.push_back(edge(curSta, j));//找到去往终点站的路线，保存路径并退出
return;
}
}
}
}
return;
}
void searchPath() {//搜索路径
int len = path.size();
int curSta = path[len - 1].startSta;//终点站的前一站位置
ans.push_back(path[len - 1].endSta);//终点站加入到ans数组
for (int i = len - 2; i >= 0; i--) {//遍历查找如何从起点站到终点站
int sta = path[i].endSta;
if (sta == curSta) {//判断该站终点是否为上一站起点
ans.insert(ans.begin(), sta);
curSta = path[i].startSta;
}
}
}
// author:@nepu_bin
// bincode.blog.csdn.net
int main() {
//初始化站点信息 哪些站可以互通，只保存了单向，遍历时可以双向在邻接矩阵标记
vector<edge> stas{ edge(0,1),edge(1,2),edge(2,8),edge(2,13),
edge(2,3),edge(3,4),edge(4,5),edge(5,6),
edge(6,7),edge(8,9),edge(9,10),edge(10,5),edge(13,12),edge(12,11),edge(11,5) };
initStaInf(stas);
printMatrix();
char tmp ;
cout << "请输入始发站(A ~ E):"<<endl;
cin >> tmp;
sstation = tmp - 'A';
cout << "请输入终点站(A ~ E):" << endl;
cin >> tmp;
estation = tmp - 'A';
bfs();
searchPath();
cout << endl << "从" << stations[sstation] << "到" << stations[estation] << "最短路线为:" << endl;
for (int i = 0; i < ans.size() - 1; i++) {
cout << stations[ans[i]] << "->";
}
cout << stations[estation];
cout << "共计 " << ans.size() << " 站" << endl;
return 0;
}
运行效果由A站 去往 K站：由D站 去往 M站由于时间仓促，暂时只测试了一部分案例。若出现错误请及时告知，阿里嘎多！}