华为2014上机考试样题_高级题_地铁换乘最短路径_无向无权图+邻接表存储+BFS广度优先算法

/*
Copyright (c) 2013, binzhouweichao@163.com

无向无权图 邻接表存储 BFS广度优先算法搜索
涉及：图 链表 队列 指针 数组 字符串 类型转换

供参考

*/

/*

A10-----A11-----A12-----A13
| |
B1--B2--B3--B4--B5--T1--B6--B7--B8--B9--B10--T2--B11--B12--B13--B14--B15
| |
A9 A14
| |
A8 A15
| |
A7 A16
| |
A6 A17
| |
A5---A4---A3---A2---A1---A18

*/

#include
#include //用到字符串操作
#include //int转string，用到流操作

using namespace std; //标准库命名空间

#define DEBUG //是否为调试模式

#define VerNum 35 //定义顶点数为35 = 18(A) + 15(B) + 2(T)
#define NULL 0 //定义空指针

typedef int Boolean; //定义布尔类型，为int类型别名，适用于访问标志visited
#define TRUE 1 //定义TRUE为1
#define FALSE 0 //定义FALSE为0

/*********************字符串数组与编号映射*************************************

A
data: A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

B
data: B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15
index: 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

T
data: T1 T2
index: 33 34

*/
string Data[VerNum]; //字符串数组，用于存储输入的字符串，数据和下标构成上述映射关系
//全局变量。。
string intToString(int index) //int转string，用于下述initD()的字符串序号
{
stringstream str1;
string str2;
str1 << index;
str1 >> str2;
return str2;
}
void InitData() //初始化字符串数组，完成映射
{
int index;
//A1-A18, index 0-17
for(index=0; index<18; index++)
{
Data[index] = "A" + intToString(index+1);
}
//B1-B15, index 18-32
for(index=18; index<33; index++)
{
Data[index] = "B" + intToString(index-18+1);
}
//T1-T2, index 33-34
Data[33] = "T1";
Data[34] = "T2";
}
/*********************************************************************************************/

int dataToIndex(string str) //查找输入字符串的相应index
{
int index;
for(index=0; index {
if(strcmp(str.c_str(), Data[index].c_str()) == 0) //比较输入字符串str与数据数组Data[]的各元素，相等则返回该元素下标index
break;
}
return index;
}

/**************************************************************邻接表存储图信息******************************