0001 /* 0002 * (有向)图的深度优先遍历算法模板 0003 */ 0004 0005 package dsa; 0006 0007 public abstract class DFS extends GraphTraverse { 0008 //变量 0009 protected static int clock = 0;//遍历过程中使用的计时钟 0010 0011 //构造方法 0012 public DFS(Graph g) { super(g); } 0013 0014 //深度优先遍历算法 0015 protected Object traverse(Vertex v, Object info) {//从顶点v出发,做深度优先查找 0016 if (UNDISCOVERED != v.getStatus()) return null;//跳过已访问过的顶点(针对非连通图) 0017 v.setDStamp(clock++); v.setStatus(DISCOVERED); visit(v, info);//访问当前顶点 0018 for (Iterator it = v.outEdges(); it.hasNext();) {//检查与顶点v 0019 Edge e = (Edge)it.getNext();//通过边e = (v, u) 0020 Vertex u = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u 0021 switch (u.getStatus()) {//根据u当前的不同状态,分别做相应处理 0022 case UNDISCOVERED ://若u尚未被发现,则 0023 e.setType(TREE);//e被归类为“树边” 0024 traverse(u, info);//从u出发,继续做深度优先查找 0025 break; 0026 case DISCOVERED ://若u已经被发现,但对其访问尚未结束,则 0027 e.setType(BACKWARD);//将e归类为“后向跨边” 0028 break; 0029 default ://VISITED,即对u的访问已经结束 0030 if (u.getDStamp() < v.getDStamp())//若相对于v,u被发现得更早,则 0031 e.setType(CROSS);//将e归类为“横跨边” 0032 else//否则 0033 e.setType(FORWARD);//将e归类为“前向跨边” 0034 break; 0035 } 0036 }//至此,v的所有邻居都已访问结束,故 0037 v.setFStamp(clock++); v.setStatus(VISITED);//将v标记为VISITED 0038 return null;//然后回溯 0039 } 0040 }