0001 /* 0002 * (有向)图的广度优先遍历算法模板 0003 */ 0004 0005 package dsa; 0006 0007 public abstract class BFS extends GraphTraverse { 0008 //构造方法 0009 public BFS(Graph g) { super(g); } 0010 0011 //广度优先遍历算法 0012 protected Object traverse(Vertex s, Object info) {//从顶点s出发,做广度优先查找 0013 if (UNDISCOVERED != s.getStatus()) return null;//跳过已访问过的顶点(针对非连通图) 0014 Queue Q = new Queue_List();//借用一个队列 0015 s.setStatus(DISCOVERED);//发现s后 0016 Q.enqueue(s);//随即令其入队 0017 visit(s, null);//并访问之 0018 while (!Q.isEmpty()) {//在队列变空之前 0019 Vertex v = (Vertex)Q.dequeue();//取出队首顶点v 0020 for (Iterator it = v.outEdges(); it.hasNext();) {//检查与顶点v 0021 Edge e = (Edge)it.getNext();//通过边e = (v, u) 0022 Vertex u = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u 0023 if (UNDISCOVERED == u.getStatus()) {//若u尚未被发现,则 0024 e.setType(TREE);//将e归类为树边 0025 u.setStatus(DISCOVERED);//发现u后 0026 Q.enqueue(u);//随即令其入队 0027 visit(u, v);//并访问之 0028 } else {//若u已被发现,甚至已访问完毕(有向图),则 0029 e.setType(CROSS);//将e归类为跨边 0030 } 0031 }//至此,v的所有邻居都已访问结束,故 0032 v.setStatus(VISITED);//将v标记为VISITED 0033 }//while 0034 return null; 0035 } 0036 }