我们平时坐地铁去上班的时候，是否有想过，地铁是怎么计费的呢？因为地铁的线路都比较复杂，一般大城市的地铁网都是错综复杂的，比如广州，目前就有15条线路，假设一条线有20个站点，那么整个地铁网络就会有300个站点，因为地铁可以换乘，从一个起点到达一个终点，会有很多路线。我们都知道，地铁的收费是根据距离来决定的(我们这里先假设每两个站的距离都是相等的)，也就是站点越多，收费就越多，通常来说，地铁从一个起点到另外一个点，都是按照最短路径来收费的(不可能按照最长吧？)，如何找到这个最短路径呢？我们首先来看看以下简图：

1.1 数组实现方式

首先来看起点站和目的地是同一条地铁线的情况，比如从A到C站，这种计算距离是十分简单的，我们只要把整条一号线的站点组合成一个数组，就可以计算从其中某个站点到另一个站点的路程。如上图的从A到C，假设A站的id是1，C站的id是3，我们把数组的元素设置为id值，那么总费用S=每站收费*(3-1)，如果一站的收费是2元，那么从A到C就是4元。这个过程十分简单！时间复杂度是O(1)，十分高效。

1.2 无向图实现方式

起点和目的点在同一条地铁线的情况计算是十分简单的，只需要构造一个数组就能实现。但如果起点和目的地不是同一条线，那么就比较复杂了。比如从一号线的A站作为起点，去二号线的F站，可选择的走法比较多，途中就有以下两种走法：

然而在现实中，两个站点的路线可能不止两条路线了，按照地铁的计费原则，理应是选择最短路径来进行计费的，也就是上面说的路线二。那么系统是怎么找到路线二，并确定它就是最短路径呢？其实，熟悉图论的童鞋早就会想到其实地铁线路，就是个无向图。而无向图中有个经典的算法是广度优先搜索，它可以找到无向图中两点之间的最短路径。

为了方便简单实现，我们这里用站点的ID作为图的各个顶点，0代表A，1代表B，2代表C，3代表D，4代表E，5代表F，这样上面的地铁线路图就简化成下面的无向图。于是，求A—>F的最短距离问题就变成求顶点0到顶点5的最短路径。

2.1 构建站点对象

我们先构造站点对象Station，这里我们主要用到的是站点的stationId，如下代码：

2.2 用邻接表构造地铁无向图

我们使用邻接表来表示这个无向图，以下是构造出的站点邻接表。左边的数组代表所有的站点，右边的一个个链表元素代表数组中的站点邻接的站点，比如数组中id为2的站点，有两个邻接站点，分别是id为2和4。

我们用链表数组stationTable表示这张邻接表，由传入的站点列表stationList作为stationTable的数据源。光是站点还不够，站点是通过一组线路来连接起来的，这个可以通过传入两个站点调用addEdge方法，构造站点与站点的连线。

    以上就是本篇文章【带你用广度优先搜索实现地铁计费功能】的全部内容了，欢迎阅览 ！ 文章地址：http://nhjcxspj.xhstdz.com/news/3740.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 物流园资讯移动站 http://yishengsujiao.xhstdz.com/ , 查看更多