简单成都地铁信息查询系统，BFS算法实现最短路径查找

前言

最近数据结构期末作业要求做一个成都地铁信息系统，在网上查阅了相关资料之后，做了出来，因为复用性极强，且代码注释都比较详细，于是决定分享出来

思路

总的来说就是从两个文本文件中读入站点和站点信息，然后通过站点信息建图，最终通过BFS改进算法实现查找任意两个站点之间的最短路径，参照地铁线路图 这是我的github地址，里面有完全的源码，仅供参考 简单成都地铁系统实现

重要代码

以下仅有部分代码，全部代码请移步上面的传送门

Graph.java 其中的加边方法很重要

import java.util.LinkedList; public class Graph { public int num; //结点总数 /* * LinkedList<Integer> adj[] * 一个存放list的数组，其中list中存放的是对应节点的所有邻接点信息, * 如adj[1]存储的就是序列号为1的站点的所有邻接点信息,也可以理解为存储所有的边 */ public LinkedList<Integer> adj[]; /* * 图的构造方法，传入结点总数v * 将数组实例化，并将每个数组中的每个list都实例化 */ public Graph(int v){ num = v; adj = new LinkedList[v]; for(int i=0; i<v; ++i) { adj[i] = new LinkedList<>(); } } /* * 图的加边方法，传入参数，s和t，二者都是结点的序列号 *因为是无向图，所以二者的邻接点list都要存储对方的信息 */ public void addEdge(int s,int t) { adj[s].add(t); adj[t].add(s); } public int getV() { return num; } public void setV(int v) { this.num = v; } public LinkedList<Integer>[] getAdj() { return adj; } public void setAdj(LinkedList<Integer>[] adj) { this.adj = adj; } }

CDSubway.java

从文件中读取站点信息，注意有两个文件，分别是station_name.txt和station_data.txt,然后根据信息加边

public static void init() { /* * 读取station_name.txt文件中的站点名称，并存储进station_name list中 */ try { // File file = new File("E:\\eclipse\\Test\\bin\\station_name.txt"); File file = new File("src//method3//station_name.txt"); InputStreamReader reader = new InputStreamReader(new FileInputStream(file),"utf-8"); BufferedReader br = new BufferedReader(reader); String line = ""; line = br.readLine(); while (line != null) { station_name.add(line.trim()); line = br.readLine(); } } catch (Exception e) { e.printStackTrace(); } /* * 读取station_data.txt文件中的站点信息 */ try { // File file = new File("E:\\eclipse\\Test\\bin\\station_data.txt"); File file = new File("src//method3//station_data.txt"); InputStreamReader reader = new InputStreamReader(new FileInputStream(file),"utf-8"); BufferedReader br = new BufferedReader(reader); String line = ""; line = br.readLine(); while (line != null) { String[] sArray=line.split(","); //以,为分隔符，将每一行划分为三个字符串存入sArray中 //将数组中的三个字符串分别存放进三个list中，因此三个list中的相同位置存放的都是一个站点的信息 lstation_name.add(sArray[0].trim()); lline_name.add(sArray[1].trim()); lstation_num.add(sArray[2].trim()); //将站点划分到各自的路线中，通过sArray[1]来判断 switch(sArray[1]) { case "1":line1.add(sArray[0]);break; case "2":line2.add(sArray[0]);break; case "3":line3.add(sArray[0]);break; case "4":line4.add(sArray[0]);break; case "7":line7.add(sArray[0]);break; case "10":line10.add(sArray[0]);break; } line = br.readLine(); //读取下一行，直到读完整个文件 } // while循环结束后，所有的站点信息都被录入完毕，现在将所有线路list放入之前创建的Set对象中方便调用 lineSet.add(line1); lineSet.add(line2); lineSet.add(line3); lineSet.add(line4); lineSet.add(line7); lineSet.add(line10); } catch (Exception e) { e.printStackTrace(); } int size=lstation_name.size(); //size表示的是站点信息的多少，因为一个站点可能有多个信息（就是指换乘站）， /* * 到目前为止，graph中只有结点，还没有边，现在开始加边 * 每次对两个站点信息进行遍历，判断是否要加边 * 加边的条件，处在同一条路线上，且序列号连续 * 因为每个站点一定都处在至少一条线路上，这样即使是中转站也可以完成加边， * 如一品天下是二号线和七号线的中转站，那么在station_data.txt中就有两个一品天下的信息，分别是一品天下,2,9和一品天下,7,1 * 这样一品天下站点的所有邻接点都能找到，自然就可以加边了 */ for(int i=1;i<size;i++) { if((lline_name.get(i)).equals(lline_name.get(i-1))&&Integer.parseInt(lstation_num.get(i))==Integer.parseInt(lstation_num.get(i-1))+1) { int x=search(lstation_name.get(i)); //通过search方法获取当前站点在lstation_name中的序列号，因为graph中的LinkedList（邻接点数组）和lstation_name 的序列号是一一对应的 int y=search(lstation_name.get(i-1)); //同上 graph.addEdge(x, y); //调用加边方法进行加边 } } }

改进BFS算法求最短距离，普通的BFS算法是无法求取最短距离的，只能广度遍历图中的所有结点，所以我们需要改进，改进的地方有两点分别是引入prev[]数组（用于保存线路信息）和终止条件，即查找到终点就退出查找。

public void calc(int start,int end,Graph graph){ if(start<0||end<0) { return; } if(start==end) { System.out.println("两站点相同"); return; } int v=graph.getV(); //得到结点总数 LinkedList<Integer>[] adj=graph.getAdj(); //得到所有边的信息 boolean[] visited = new boolean[v]; //创建访问数组 visited[start] = true; //设置初始站点已被访问过 Queue<Integer> queue = new LinkedList<>(); //创建辅助队列 queue.add(start); int[] prev = new int[v]; //路径数组，记录站点的前一个站点，如prev[q]=w,就表示想要到达q，就必须先经过w for(int i=0; i<v;i++) { //初始化为-1 prev[i] = -1; } while(queue.size() != 0) { int w =queue.poll(); for(int i=0; i<adj[w].size();++i) { //遍历站点 w 的所有邻接站点 int q = adj[w].get(i); //取出 w 的邻接站点 if(!visited[q]) { //判断是否访问过 prev[q] = w; //加入路径数组 if(q == end) { //如果是终点就结束，调用print方法打印路径 print(prev,start,end); return; } visited[q] = true; //如果不是目的地，就设置为已访问过， queue.add(q); //邻接站点入队 } } } }

因为从prev[]中获取的是路径的逆序，即从终点到起点，所以我们需要，将路径中的结点一个一个取出来，压栈，最后出栈就是正确的顺序了，调用print()函数实现打印路径

private void print(int[] prev, int start,int end) { int end2=end; //将end赋值给end2，之后会用到 int num=1; //用于记录经过的站数，初值为1 Stack<Integer> stack=new Stack<Integer>(); //创建辅助栈 /* * 依次将路径数组中的值入栈，利用栈后进先出的特性 * 循环条件1：prev[end]!=-1 表示已经找到了正确路线， * 循环条件2：start!=end，表示已经全部压栈完毕 */ while(prev[end]!=-1&&start!=end){ stack.push(prev[end]); //目的地的前一个站点入栈 end=prev[end]; //将目的地设为目的地的前一个站点，这样循环下去，最终end=start 结束循环 } List<String> line = new ArrayList<String>(); //创建辅助list line /* * 将栈里的数据依次出栈，并将序列号转换成站名，放进list */ while(!stack.empty()){ //只要栈不空 int e=stack.pop(); //出栈 String name=new CDSubway().station_name.get(e); //调用CDSubway的静态变量station_name，根据序列号获取站名 line.add(name); //将站名加入list } String name=new CDSubway().station_name.get(end2); //通过之前保存的end2，获取目的地站名，因为end会变化 line.add(name); //加入list System.out.print(line.get(0)); //对线路上每一个站点进行遍历（从第二个站点开始，倒数第二个站点结束），判断与前后两个站点是否发生了换乘 for(int i=1;i<line.size()-1;i++) { /* * 之所以3个站点要一前一后一共四次调用transfer方法是因为一条路线有两个方向 * 如顺着走就是高新，火车南站，三瓦窑，逆着走就是三瓦窑，火车南站，高新 * 注，地铁并没有顺逆的方向，这里的顺逆是指的我的station_data文件中标注的顺序 */ int x=transfer(line.get(i-1),line.get(i)); int y=transfer(line.get(i),line.get(i-1)); int x1=transfer(line.get(i),line.get(i+1)); int y1=transfer(line.get(i+1),line.get(i)); if(x<=0) { //说明逆着走 x=y; } if(x1<=0) { //说明逆着走 x1=y1; } if(x==x1) { //表示没换乘 System.out.print("->"+line.get(i)); num++; } else { //表示换乘 System.out.print("->"+line.get(i)+"(换乘"+num(x1)+")"); num++; } } System.out.println("->"+line.get(line.size()-1)); System.out.println("共"+num+"站"); }

关于文件格式

关于复用

你只需要准备好类似的station_name.txt和station_data.txt文件，再将代码中有关地铁线路信息的部分修改成自己的，即可实现复用

码字不易，如果觉得有用，麻烦点个赞，点个关注好吗，秋梨膏！！！ 如需转载，请注明出处！！！

参考文章： 无权图地铁求最短路径

带权图地铁求最短路径