讲一下自己的思路，因为是无权路径，所以我用BFS来求最短路径，得到最短路径后，两点确定一条线路，来判断换乘信息。
这是Station类的代码
public class Station {
private String Station_name; //存放站点名
private ArrayList<String> Line = new ArrayList<String>(); //存放站点所在的线路
private ArrayList<Station> Linkstation = new ArrayList<Station>(); //存放相邻的站带你
public int dist;
public Station pre; //存放最短路径的前驱节点public ArrayList<Station> getLinkstation() {
return Linkstation;
}
public void setLinkstation(ArrayList<Station> linkstation) {
Linkstation = linkstation;
}
public void addLinkstation(Station station) {
Linkstation.add(station);
}
public String getStation_name() {
return Station_name;
}
public void setStation_name(String station_name) {
Station_name = station_name;
}
public void addLine(String line) {
Line.add(line);
}
public ArrayList<String> getLine() {
return Line;
}
public void setLine(ArrayList<String> line) {
Line = line;
}
}
求最短路径的代码，因为是无权路径，就用BFS来求了
public static void shortestPath(Station station){
Queue<Station> queue = new LinkedList<>();
station.dist=0;
queue.offer(station);
while(!queue.isEmpty()) {
Station vertex=queue.poll();
for(Station linkstation:vertex.getLinkstation()) {
if(linkstation.dist==MaxValue) {
linkstation.dist=vertex.dist+1;
queue.offer(linkstation);
linkstation.pre=vertex;
}
}
}
}
判断换乘的代码
String changeLine=getSameLine(shortestPath.get(0),shortestPath.get(1));
for(int i=0;i<shortestPath.size();i++) {
if(i>=2) {
if(!getSameLine(shortestPath.get(i),shortestPath.get(i-1)).equals(changeLine)) {
changeLine=getSameLine(shortestPath.get(i),shortestPath.get(i-1));
System.out.println("------->换乘"+changeLine);
}
}
System.out.println(shortestPath.get(i).getStation_name());
}
}
主要思路就是先判断前两个站点的线路，存储在changeLine里，然后从第三个站点开始，循环判断第i-1个站点，到第i个站点的连线是不是和changeLine一样，如果不一样就输出换乘信息，并且更新changeLine。
全部代码:
package subway;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class TestClass {
static final int MaxValue=65535;
static final int MaxNum=400;
public static void main(String[] args) {
System.out.print("请输入地铁文件路径:");
Scanner input=new Scanner(System.in);
File file = new File(input.nextLine());
ArrayList<Station> stations= new ArrayList<>();
try{
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file), "UTF-8"));
String s = null;
int j;
Station last_station= new Station();
while ((s = br.readLine()) != null) {
String tokens[]=s.split(" ");
for(int i=1;i<tokens.length;i++) {
for(j=0;j<stations.size();j++) {
if(stations.get(j).getStation_name().equals(tokens[i]))
{
stations.get(j).addLine(tokens[0]);
if(i!=1) {
stations.get(j).addLinkstation(last_station);
last_station.addLinkstation(stations.get(j));
}
last_station=stations.get(j);
break;
}
}
if(j==stations.size()) {
Station station = new Station();
station.addLine(tokens[0]);
station.setStation_name(tokens[i]);
station.dist=MaxValue;
if(i!=1) {
station.addLinkstation(last_station);
last_station.addLinkstation(station);
}
stations.add(station);
last_station=station;
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
System.out.print("请输入起始站：");
String begin_station_name=input.next();
System.out.print("请输入终点站：");
String end_station_name=input.next();
Station end_station = new Station();
Station begin_station = new Station();
for(Station station:stations) {
if(station.getStation_name().equals(begin_station_name)) {
begin_station=station;
shortestPath(station);
}
if(station.getStation_name().equals(end_station_name))
end_station=station;
}
ArrayList<Station> shortestPath=new ArrayList<Station>();
showPath(end_station,shortestPath);
String changeLine=getSameLine(shortestPath.get(0),shortestPath.get(1));
for(int i=0;i<shortestPath.size();i++) {
if(i>=2) {
if(!getSameLine(shortestPath.get(i),shortestPath.get(i-1)).equals(changeLine)) {
changeLine=getSameLine(shortestPath.get(i),shortestPath.get(i-1));
System.out.println("------->换乘"+changeLine);
}
}
System.out.println(shortestPath.get(i).getStation_name());
}
}
public static void shortestPath(Station station){
Queue<Station> queue = new LinkedList<>();
station.dist=0;
queue.offer(station);
while(!queue.isEmpty()) {
Station vertex=queue.poll();
for(Station linkstation:vertex.getLinkstation()) {
if(linkstation.dist==MaxValue) {
linkstation.dist=vertex.dist+1;
queue.offer(linkstation);
linkstation.pre=vertex;
}
}
}
}
public static void showPath(Station end_station,ArrayList<Station> result) {
if(end_station.pre!=null)
showPath(end_station.pre,result);
result.add(end_station);
}
private static String getSameLine(Station station1,Station station2) {
for(String line1:station1.getLine()) {
for(String line2:station2.getLine()) {
if(line1.equals(line2))
return line1;
}
}
return null;
}
}
测试用例：
1.单线站点-单线站点
2.换乘站-换乘站
3.输入错误的站点