0001 /* 0002 * (有向)图的遍历算法模板 0003 */ 0004 0005 package dsa; 0006 0007 public abstract class GraphTraverse { 0008 //常量 0009 final static int UNDISCOVERED = 0;//尚未被发现的顶点 0010 final static int DISCOVERED = 1;//已被发现的顶点 0011 final static int VISITED = 2;//已访问过的顶点 0012 final static int UNKNOWN = 0;//未知边 0013 final static int TREE = 1;//树边 0014 final static int CROSS = 2;//横跨边 0015 final static int FORWARD = 3;//前向跨边 0016 final static int BACKWARD = 4;//后向跨边 0017 0018 //变量 0019 protected Graph G;//图 0020 0021 //构造方法 0022 public GraphTraverse(Graph g) { G = g; } 0023 0024 //将G中各顶点的标志、各边的分类复位(s为遍历起点) 0025 protected void reset(Vertex s) { 0026 for (Iterator it = G.vertices(); it.hasNext();) {//所有 0027 Vertex v = (Vertex)it.getNext();//顶点的 0028 v.setStatus(UNDISCOVERED);//状态置为UNDISCOVERED 0029 v.setDistance(Integer.MAX_VALUE);//最短距离初始化为无穷大 0030 } 0031 for (Iterator it = G.edges(); it.hasNext();)//所有边 0032 ((Edge)it.getNext()).setType(UNKNOWN);//置为UNKNOWN 0033 } 0034 0035 //遍历过程中对顶点v的具体访问操作的模板:取决于、服务于具体的算法algorithm() 0036 protected abstract Object visit(Vertex v, Object info); 0037 0038 //基于遍历操作实现的其它算法的模板:s为起始顶点,info向算法传递参数及保存算法的返回信息 0039 public abstract Object algorithm(Vertex s, Object info); 0040 0041 //遍历算法模板 0042 protected abstract Object traverse(Vertex v, Object info);//从顶点v出发做遍历 0043 }