设计文档
3、算法设计
3.1站站查询
本系统设计采用优先考虑换乘次数最少的路径，其次考虑经过最少站台数的搜索算法。
A．寻找最少换乘次数
首先是公交网络系统的抽象表示，使用了邻接矩阵的改进方法——邻接表。通过表结构的形式可以大
量节省内存空间。
邻接表示图如下：
若两个站台 Si 与 Sj 通过线路 Lk 可直达，则表中的信息如下：
邻接表的构造方法如下：
设南京地区的公交站台总数为n，从0开始，我们对每一个站台进行编号。Si表示的是编号为i
（i∈[0,n]）的站台。设公交线路总数为m，同样从0开始，我们对每一个公交线路进行编号。Lj表示的
是编号为j（j∈[0,m]）的公交线路。当Si→Sj有一条线路直达时，表中对应的位置则存储直达路线；当
两个站台之间有多个直达路径时，则矩阵中各个元素的值应该是一个变长的数组，它存储了所有直达
线路的索引编号。
利用生成的邻接表我们可以方便的构建换乘一次路线、换乘两次路线等等。
1）构建换乘一次路线：
若两个站台Si→Sj不可达，但它们之间可以通过一次转乘之后可达，则必定存在一个站台Sk使得，站台
Si→Sk可达，同样站台Sk→Sj可达。
这样，我们如果找到了一个符合这样条件的站台Sk，我们就可以将这个站台当作一次转乘的中转站，
并构建一条换乘一次的路径。
2）构建换乘两次路线：
评论0