0001 /* 0002 * (有向)图基于BFS的最短距离算法 0003 */ 0004 0005 package dsa; 0006 0007 public class BFSDistance extends BFS { 0008 //构造方法 0009 public BFSDistance(Graph g) { super(g); } 0010 0011 //顶点访问操作:在本算法中,info是顶点v的前驱 0012 protected Object visit(Vertex v, Object info) { 0013 if (null == info)//v为BFS的起始顶点 0014 v.setDistance(0); 0015 else 0016 v.setDistance(((Vertex)info).getDistance() + 1); //设置v到s的距离 = 前驱的距离+1 0017 return null; 0018 } 0019 0020 //基于BFS实现的最短距离算法:s为起始顶点,info向算法传递参数 0021 public Object algorithm(Vertex s, Object info) { 0022 reset(s); 0023 traverse(s, info);//BFS:到起点的最短距离记录在各顶点的distance域中 0024 return null; 0025 } 0026 }