0001 /* 0002 * (有向)带权图最小生成树的Prim-Jarnik算法 0003 */ 0004 0005 package dsa; 0006 0007 public class BestFSPrim extends BestFS { 0008 //构造方法 0009 public BestFSPrim(Graph g) { super(g); } 0010 0011 //更新尚未访问的顶点到已访问集的最短距离 0012 protected void updateDistanceAfter(Vertex v) { 0013 for (Iterator it = v.outEdges(); it.hasNext();) {//检查与顶点v 0014 Edge e = (Edge)it.getNext();//通过边e = (v, w) 0015 Vertex w = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点w 0016 int weight = ((Integer)e.getInfo()).intValue();//根据边(v, w)的权重 0017 if (w.getDistance() > weight) {//取原距离与新距离中的小者 0018 w.setDistance(weight); 0019 w.setBFSParent(v); 0020 } 0021 } 0022 } 0023 }