3.17双人总结

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;
}
}

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);      //邻接站点入队
}
}
}
}

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+"站");
}