上一篇文章写了关于铁路购票相关的业务逻辑 铁路购票软件应该怎么设计
另外一个问题是"公交换乘"问题，从A到B的所有可行的路径。
这个问题如果单纯地存储线路+站点数据 t_line/t_site，对于多次换乘的情况很难处理，需要用到"图"
(1)图：图由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为"邻居"；
(2)广度优先搜索：是一种用于图的查找的算法。
具体到公交换乘问题，除了基础的t_line/t_site之外，我们可以用"图"的数据结构来存储站点的信息，比如对于一个站点而言，我们可以存储如下的信息：code, name, neighbors(邻居站点，即从当前站点，可以到达哪些站点), transfer(是否可换乘?)
然后我们利用"广度优先搜索"算法来处理问题。
上图所示的4条公交路线，共4条线路，红色的站点表示可以换乘。
16路： A->B->C->D
2路： E->C->F->G->...
812路：I->K->L
142路：G->H->I->J
那么我们可以利用"散列表"来存储图(graph)信息
Map<String, List> siteMap = new HashMap<>();
// 各个站点的节点信息
siteMap.put("A", Arrays.asList("B"));
siteMap.put("B", Arrays.asList("A", "C"));
siteMap.put("C", Arrays.asList("B", "D", "E", "F"));
siteMap.put("D", Arrays.asList("C"));
siteMap.put("E", Arrays.asList("C"));
siteMap.put("F", Arrays.asList("C", "G"));
siteMap.put("G", Arrays.asList("F", "H"));
siteMap.put("H", Arrays.asList("G", "I"));
siteMap.put("I", Arrays.asList("H", "J", "K"));
siteMap.put("J", Arrays.asList("I"));
siteMap.put("K", Arrays.asList("I", "L"));
siteMap.put("L", Arrays.asList("K"));
如果我们要找到从A到K的路线，该用怎样的算法？
1. 我们利用一个队列，表示需要查找的站点，队列的第一个元素（站点）就是起始点，即站点A；
2.遍历队列中的元素，如果元素与终点值(K)一致，则表示找到了路线；如果没有，则把该元素(站点)的邻居(未搜索的)加入到队列中继续搜索，直到队列为空；
3. 创建一个对象searched，表示已经搜索的元素，防止重复搜索/死循环。
为了输出路线信息，我们创建2个对象：
SearchLine表示搜索过程中的每一条可能的路线；
Route 表示路线中的某一路段，比如 A->B 表示一个路段；
一条SearchLine中包含多个Route。
具体的代码逻辑如下所示：
Route.java
public class Route implements Serializable {
private String from;
private String to;
public Route() {
}
public Route(String from, String to) {
this.from = from;
this.to = to;
}
public String getFrom() {
return from;
}
public void setFrom(String from) {
this.from = from;
}
public String getTo() {
return to;
}
public void setTo(String to) {
this.to = to;
}
}
SearchLine.java
/**
* 一条可能的搜索线路
*/
public class SearchLine implements Serializable {
/**
* 路线的拼接，A -> B 作为一个Route
*/
private List<Route> routeList = new LinkedList<>();
/**
* 从“起始地”到“目的地”的距离
*/
private String distance;
public SearchLine() {
}
public SearchLine(String from, String to) {
Route route = new Route(from, to);
routeList.add(route);
}
public SearchLine(List<Route> routeList) {
this.routeList = new LinkedList<>();
for (Route route : routeList) {
this.routeList.add(route);
}
}
public void addRoute(String from, String to) {
Route route = new Route(from, to);
routeList.add(route);
}
public List<Route> getRouteList() {
return routeList;
}
public void setRouteList(List<Route> routeList) {
this.routeList = routeList;
}
public String getDistance() {
return distance;
}
public void setDistance(String distance) {
this.distance = distance;
}
}
搜索路线的代码
public class BusLineTest {
/**
* 利用散列表来实现Graph
*/
@Test
public void testGraph() {
Map<String, List> siteMap = new HashMap<>();
// 各个站点的节点信息
siteMap.put("A", Arrays.asList("B"));
siteMap.put("B", Arrays.asList("A", "C"));
siteMap.put("C", Arrays.asList("B", "D", "E", "F"));
siteMap.put("D", Arrays.asList("C"));
siteMap.put("E", Arrays.asList("C"));
siteMap.put("F", Arrays.asList("C", "G"));
siteMap.put("G", Arrays.asList("F", "H"));
siteMap.put("H", Arrays.asList("G", "I"));
siteMap.put("I", Arrays.asList("H", "J", "K"));
siteMap.put("J", Arrays.asList("I"));
siteMap.put("K", Arrays.asList("I", "L"));
siteMap.put("L", Arrays.asList("K"));
SearchLine searchLine = search(siteMap, "A", "K");
if (searchLine == null) {
System.out.println("未找到路线");
} else {
List<Route> routeList = searchLine.getRouteList();
for (Route route : routeList) {
System.out.println("从" + route.getFrom() + "到" + route.getTo());
}
}
}
/**
* 创建一个对象: 搜索队列（默认有一个，即起始点）
* 搜索队列中每个站点的邻居，如果包含了目的站点，则结束；如果不包含，就报所有邻居都加入搜索队列（去除重复的）
*/
public SearchLine searchIt(Map<String, List> siteMap, Queue searchQueue, List<String> searched, String to) {
// 所有可能的线路
List<SearchLine> searchLineList = new ArrayList<>();
while (!searchQueue.isEmpty()) {
String neighbor = (String)searchQueue.poll(); // 返回第一个元素，并在队列中删除
if (neighbor.equals(to)) {
return getLine(to, searchLineList);
}
searched.add(neighbor);
// 获取 neighbor 的邻居，并加入到queue(去重)
List<String> neighbors = siteMap.get(neighbor);
if (neighbors != null && neighbors.size() > 0) {
// 从当前路线中寻找以neighbor结尾的路线，并增加x条新路线，删除原先的（searchLine）
SearchLine searchLine = getLine(neighbor, searchLineList);
for (String site : neighbors) {
if (!searched.contains(site)) {
if (searchLine == null) {
// 新增一条路线
searchLineList.add(new SearchLine(neighbor, site));
} else {
// 更新路线（在原先的基础上，新增一条路线，比如原先A->B, 新增1条 A->B->C）
SearchLine newLine = new SearchLine(searchLine.getRouteList());
newLine.addRoute(neighbor, site);
searchLineList.add(newLine);
}
searchQueue.add(site);
}
}
}
}
return null;
}
/**
* 查找以site结尾的线路 line
* @param site
* @param searchLines
* @return
*/
private static SearchLine getLine(String site, List<SearchLine> searchLines) {
for (SearchLine line : searchLines) {
// 当前的 路段
List<Route> routeList = line.getRouteList();
if (routeList == null || routeList.size() == 0) {
return null;
}
// 找到以site结尾的路线
Route route = routeList.get(routeList.size() - 1);
if (route.getTo().equals(site)) {
SearchLine searchLine = new SearchLine(line.getRouteList());
// 删除line
searchLines.remove(line);
// 返回
return searchLine;
}
}
return null;
}
/**
* @param siteMap
* @param from
* @param to
* @return
*/
private SearchLine search(Map<String, List> siteMap, String from, String to) {
// 待搜索的队列
Queue<String> queue = new LinkedList<>();
queue.add(from);
// 已搜索的站点
List<String> searched = new ArrayList<>();
return searchIt(siteMap, queue, searched, to);
}
}