0001 /* 0002 * (有向)带权图最佳优先遍历 0003 */ 0004 0005 package dsa; 0006 0007 public abstract class BestFS extends GraphTraverse { 0008 //构造方法 0009 public BestFS(Graph g) { super(g); } 0010 0011 //更新尚未访问的顶点到已访问点集的最短距离(取决于具体的算法) 0012 protected abstract void updateDistanceAfter(Vertex v); 0013 0014 //最佳优先遍历算法 0015 protected Object traverse(Vertex s, Object info) {//从顶点s出发,做最佳优先遍历 0016 if (UNDISCOVERED != s.getStatus()) return null;//跳过已访问过的顶点(针对非连通图) 0017 s.setDistance(0);//设置s到已访问点集的距离 0018 Vertex v;//最佳顶点 0019 while (null != (v = bestVertex())) {//只要还有最佳顶点 0020 visit(v, null);//在发现并访问v之后 0021 updateDistanceAfter(v);//更新尚未访问的顶点到已访问集的最短距离 0022 }//while 0023 return null; 0024 } 0025 0026 //顶点访问操作:在本算法中,info无用 0027 protected Object visit(Vertex v, Object info) { 0028 v.setStatus(VISITED);//设置“已访问”标记 0029 return null; 0030 } 0031 0032 //基于BestFS实现的最短距离算法:s为起始顶点,info向算法传递参数 0033 public Object algorithm(Vertex s, Object info) { 0034 reset(s);//初始化,标记复位 0035 traverse(s, info);//BestFS:到起点的最短距离记录在各顶点的distance域中 0036 return null; 0037 } 0038 0039 //从尚未访问的顶点中选出最佳者 0040 //对于Dijkstra算法而言,就是与已访问集连通、距离最近的顶点(及距离不是无穷的最近顶点) 0041 //若没有这样的顶点,则返回null 0042 protected Vertex bestVertex() { 0043 int bestValue = Integer.MAX_VALUE;//最佳指标(越小越好) 0044 Vertex bestVertex = null;//最佳顶点 0045 for (Iterator it = G.vertices(); it.hasNext();) {//逐个检查 0046 Vertex u = (Vertex)it.getNext();//各个 0047 if (UNDISCOVERED == u.getStatus())//尚未访问的顶点u 0048 if (bestValue > u.getDistance())//若u到已访问点集距离更近,则 0049 { bestValue = u.getDistance(); bestVertex = u; }//更新最佳记录 0050 } 0051 if ((null != bestVertex) && (null != bestVertex.getBFSParent()))//最佳顶点与其父亲之间的联边 0052 G.edgeFromTo(bestVertex.getBFSParent(), bestVertex).setType(TREE);//被标记为TREE 0053 return bestVertex; 0054 } 0055 }