算法思想：存储图数据，运用广度优先搜索遍历找寻答案。
主要/核心函数分析：//寻找经过站点最少的方案 void FindLeastStationNum(BusMap& M, int StartStation, int EndStation)先将终点站点入队，然后出队遍历经过该站点的公交线路并找到该站点对应公交线路的线内ID然后搜索该ID前后没有访问的站点入队，直到找到起点就输出该条路线。运用k巧妙存储线路前后结点信息。//寻找转车最少的方案void FindLeastTransfer(BusMap& M, int StartStation, int EndStation)与前面不同的是，它是遍历该路公交车的所有站点入栈再接着遍历经过它的其他公交线路上的站点，以及如果经过该站点的公交线路上有起点直接输出该线路即可。
1 #include <iostream> 2 #include <string.h> 3 #include <fstream> 4 #include <sstream> 5 #include <string> 6 #include <windows.h> 7 using namespace std; 8 //公交线路信息 9 typedef struct Bus 10 { 11 int No; //该公交车的编号 12 int StationCount; //该公交车经过的站点数量 13 int BusRoute[70]; //该公交车依次经过的站点的数组下标 14 }Bus; 15 //站点信息 16 typedef struct Station 17 { 18 int StationName; //站点名称 19 int BusCount; //经过该站点的公交车数量 20 int bus[34]; //经过该站点的公交车的编号 21 }Station; 22 //大的公交路线图 23 typedef struct BusMap 24 { 25 Bus bus[730]; 26 Station station[6600]; 27 int BusCount; //公交车数量 28 int StationCount; //站点数量 29 }BusMap; 30 //获取站台对应的编号 31 int GetBusStation(BusMap& M, int ID) 32 { 33 for (int i = 1; i <= M.StationCount; i++) 34 { 35 if (M.station[i].StationName==ID) 36 return i; 37 } 38 return 0; 39 } 40 //更新图信息 41 void IncreaseBusStation(BusMap& M, int ID) 42 { 43 int num = GetBusStation(M, ID); 44 //该站台未创建 45 if (num == 0) 46 { 47 //纳入新的station，并将count++ 48 M.station[++M.StationCount].StationName= ID; 49 num = M.StationCount;//现在ID在站点的编号 50 } 51 //给当前公交线加入新的站点，并把该公交线的站点数量++ 52 M.bus[M.BusCount].BusRoute[M.bus[M.BusCount].StationCount++] = num; 53 //更新该站点经过的公交线路，以及经过公交数量 54 M.station[num].bus[++M.station[num].BusCount] = M.bus[M.BusCount].No; 55 } 56 //创建图 57 void CreateMap(BusMap& M) 58 { 59 M.BusCount = 0;//公交车数量 60 M.StationCount = 0;//站点总数 61 //初始化 62 for (int i = 0; i < 730; i++) 63 M.bus[i].StationCount = 1; 64 for (int i = 0; i < 6600; i++) 65 M.station[i].BusCount = 0; 66 67 int ID=0;//站点ID 68 char ch;//一个一个获取字符 69 FILE* fp; 70 if ((fp = fopen("all.txt", "r")) == NULL) 71 { 72 cout<<"文件打开失败"<<endl; 73 exit(0); 74 } 75 //获取第一个公交车ID 76 int busid = 0; 77 ch = fgetc(fp); 78 while (ch != ' ') 79 { 80 busid = busid * 10 + ch - '0'; 81 ch = fgetc(fp); 82 } 83 M.bus[++M.BusCount].No=busid;//纳入 84 85 while (1) 86 { 87 ch = fgetc(fp); 88 89 if (feof(fp)) 90 { 91 IncreaseBusStation(M, ID); 92 break;//文件结束 93 } 94 if (ch == ' ')//只找最后的站点ID 95 { 96 ID = 0; 97 continue; 98 } 99 if (ch == '\n') 100 { 101 IncreaseBusStation(M, ID); 102 ID = 0; 103 //获取公交ID 104 int busid = 0; 105 ch = fgetc(fp); 106 while (ch != ' ') 107 { 108 busid = busid * 10 + ch - '0'; 109 ch = fgetc(fp); 110 } 111 //如果和先前的不一样，则开始新的线路创建 112 if (busid != M.bus[M.BusCount].No) 113 { 114 M.bus[++M.BusCount].No = busid; 115 continue; 116 } 117 else 118 continue; 119 } 120 ID = ID * 10 + ch - '0'; 121 } 122 fclose(fp); 123 } 124 //获取公交线路对应的编号 125 int GetBus(BusMap& M, int No) 126 { 127 for (int i = 1; i <= M.BusCount; i++) 128 { 129 if (M.bus[i].No == No) 130 return i; 131 } 132 return 0; 133 } 134 //队列内部节点 135 typedef struct LNode 136 { 137 int data; 138 struct LNode* next; 139 }LNode, * QueuePtr; 140 //队列 141 typedef struct LinkQueue 142 { 143 QueuePtr front; 144 QueuePtr rear; 145 }LinkQueue; 146 //队列初始化 147 void InitQueue(LinkQueue& Q) 148 { 149 Q.front = Q.rear = (LNode*)malloc(sizeof(LNode)); 150 if (Q.front == NULL) exit(0); 151 Q.front->next = NULL; 152 } 153 //1是空，0是有 154 int QueueEmpty(LinkQueue Q) 155 { 156 if (Q.front != Q.rear) 157 return 0; 158 else 159 return 1; 160 } 161 //队列入队 162 void EnQueue(LinkQueue& Q, int e) 163 { 164 LNode* s; 165 s = (LNode*)malloc(sizeof(LNode)); 166 if (s == NULL) exit(0); 167 s->data = e; 168 s->next = NULL; 169 Q.rear->next = s; 170 Q.rear = s; 171 } 172 //队列出队 173 int DeQueue(LinkQueue& Q) 174 { 175 LNode* p; 176 int e; 177 if (Q.front == Q.rear) return -1;//队列为空 178 p = Q.front->next; 179 e = p->data; 180 Q.front->next = p->next; 181 //当前节点为尾节点 182 if (Q.rear == p) 183 Q.rear = Q.front; 184 free(p); 185 return e; 186 } 187 //NextStation记录下一站点，busno记录经过该站所乘坐的公交车 188 typedef struct info 189 { 190 int NextStation; 191 int busno; 192 int visited; 193 }info; 194 195 info k[6600];//记录行走路线的信息 196 //寻找经过站点最少的方案 197 void FindLeastStationNum(BusMap& M, int StartStation, int EndStation) 198 { 199 //记录站点在数组中的下标 200 int start = GetBusStation(M, StartStation); 201 int end = GetBusStation(M, EndStation); 202 203 //初始化 204 for (int i = 1; i < 6600; i++) 205 { 206 k[i].visited = 0;//标记该结点是否访问过 207 k[i].NextStation = i; 208 k[i].busno = 0; 209 } 210 211 LinkQueue Q; 212 InitQueue(Q); 213 EnQueue(Q, end); 214 //倒序查找 215 k[end].visited = 1; 216 217 while (Q.front != Q.rear)//队列不为空 218 { 219 end = DeQueue(Q); 220 //遍历所有经过此站的线路 221 for (int i = 1; i <= M.station[end].BusCount; i++) 222 { 223 //获取该编号公交车对应大Map中bus数组的下标 224 int b = GetBus(M, M.station[end].bus[i]); 225 //遍历该路公交车，找到该站点对应的该公交线路的第几站 226 for (int j = 1; j < M.bus[b].StationCount; j++) 227 { 228 if (M.bus[b].BusRoute[j] == end) 229 { 230 //下一站或上一站为起始站 231 if (M.bus[b].BusRoute[j + 1] == start || M.bus[b].BusRoute[j - 1] == start) 232 { 233 int count = 0; 234 235 int bus = k[end].busno;//start后一个站点的公交 236 237 cout << M.station[start].StationName<<"(乘坐"<<M.bus[b].No<<"路)->"; 238 while (end != GetBusStation(M, EndStation)) 239 { 240 cout << M.station[end].StationName; 241 cout << "(乘坐 " << bus << "路)->"; 242 243 end = k[end].NextStation; 244 bus = k[end].busno; 245 count++; 246 } 247 cout << M.station[end].StationName << "(到达终点，下车)" << endl; 248 cout << "最少经过" << count+1 << "个站点" << endl; 249 return; 250 } 251 //当前一站存在且未被访问 252 if (j - 1 > 0) 253 { 254 if (k[M.bus[b].BusRoute[j - 1]].visited == 0) 255 { 256 k[M.bus[b].BusRoute[j - 1]].busno = M.bus[b].No; 257 k[M.bus[b].BusRoute[j - 1]].NextStation = end; 258 EnQueue(Q, M.bus[b].BusRoute[j - 1]); 259 k[M.bus[b].BusRoute[j - 1]].visited = 1; 260 } 261 } 262 //当后一站存在且未被访问 263 if (j + 1 < M.bus[b].StationCount) 264 { 265 if (k[M.bus[b].BusRoute[j + 1]].visited == 0) 266 { 267 k[M.bus[b].BusRoute[j + 1]].busno = M.bus[b].No; 268 k[M.bus[b].BusRoute[j + 1]].NextStation = end; 269 EnQueue(Q, M.bus[b].BusRoute[j + 1]); 270 k[M.bus[b].BusRoute[j + 1]].visited = 1; 271 } 272 } 273 break;//找到第几站就不用继续for了 274 } 275 } 276 } 277 } 278 } 279 //寻找转车最少的方案 280 void FindLeastTransfer(BusMap& M, int StartStation, int EndStation) 281 { 282 int start = GetBusStation(M, StartStation); 283 int end = GetBusStation(M, EndStation); 284 for (int i = 1; i < 300; i++) 285 { 286 k[i].visited = 0; 287 k[i].NextStation = i; 288 k[i].busno = 0; 289 } 290 291 LinkQueue Q; 292 InitQueue(Q); 293 EnQueue(Q, end); 294 k[end].visited = 1; 295 296 //队列不为空 297 while (Q.front != Q.rear) 298 { 299 end = DeQueue(Q); 300 //遍历所有经过该站点的公交车路线 301 for (int i = 1; i <= M.station[end].BusCount; i++) 302 { 303 int b = GetBus(M, M.station[end].bus[i]); 304 //遍历该路公交车的所有站点 305 for (int j = 1; j < M.bus[b].StationCount; j++) 306 { 307 //如果该路公交车有start结点，就直接走 308 if (M.bus[b].BusRoute[j] == start) 309 { 310 int bus = k[end].busno; 311 int count = 1; 312 cout << M.station[start].StationName<<"(乘坐"<< M.bus[b].No <<"路公交车)->"; 313 while (end!= GetBusStation(M, EndStation)) 314 { 315 316 cout << M.station[end].StationName<<"(换乘"<<bus<<"路车)->"; 317 count++; 318 319 end = k[end].NextStation; 320 bus = k[end].busno; 321 } 322 cout << M.station[end].StationName << endl; 323 cout << "至少需要乘坐" << count << "班公交车" << endl; 324 return; 325 } 326 else if (k[M.bus[b].BusRoute[j]].visited == 0) 327 { 328 k[M.bus[b].BusRoute[j]].visited = 1; 329 k[M.bus[b].BusRoute[j]].busno = M.bus[b].No; 330 k[M.bus[b].BusRoute[j]].NextStation = end;//保证该条线路都是从end发出 331 EnQueue(Q, M.bus[b].BusRoute[j]); 332 } 333 } 334 } 335 } 336 //先把经过该站点的所有公交线路上的站点入队，再一个一个搜索每个站点，直到找到一条线包含start就是最少转车 337 } 338 339 int main() 340 { 341 BusMap M; 342 CreateMap(M); 343 int start, end; 344 cout<<"请输入起始站点,和最终站点ID："<<endl; 345 cin >> start >> end; 346 while (GetBusStation(M, start) == 0 || GetBusStation(M, end) == 0) 347 { 348 cout << "站点输入有误！" << endl; 349 cout << "请重新输入起始站点,和最终站点ID："; 350 cin >> start >> end; 351 } 352 353 FindLeastStationNum(M, start, end); 354 FindLeastTransfer(M, start, end); 355 356 return 0; 357 }