一个（有向）图的深度优先遍历算法模板，以Java源码实现。
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
/* * （有向）图的深度优先遍历算法模板 */
package dsa;
public abstract class DFS extends GraphTraverse {
//变量
protected static int clock = 0; // 遍历过程中使用的计时钟
//构造方法
public DFS(Graph g) {
super(g);
}
//深度优先遍历算法
protected Object traverse(Vertex v, Object info) {
// 从顶点v出发，进行深度优先查找
if (UNDISCOVERED != v.getStatus()) return null; // 跳过已访问过的顶点（针对非连通图）
v.setDStamp(clock++);
v.setStatus(DISCOVERED);
visit(v, info); // 访问当前顶点
for (Iterator it = v.outEdges(); it.hasNext();) {
Edge e = (Edge)it.getNext(); // 通过边e = (v, u)
Vertex u = (Vertex)e.getVPosInV(1).getElem(); // 相联的每一顶点u
switch (u.getStatus()) { // 根据u当前的不同状态，分别做相应处理
case UNDISCOVERED: // 若u尚未被发现，则 e被归类为“树边”
e.setType(TREE);
traverse(u, info); // 从u出发，继续做深度优先查找
break;
case DISCOVERED: // 若u已经被发现，但对其访问尚未结束，则 e归类为“后向跨边”
e.setType(BACKWARD);
break;
default: // VISITED，即对u的访问已经结束 如果相对于v，u被发现得更早，则 e被归类为“横跨边” 否则 e归类为“前向跨边”
if (u.getDStamp() < v.getDStamp()) { //若相对于v，u被发现得更早, 则将e归类为“横跨边” else 将e归类为“前向跨边” } else{ e.setType(FORWARD);}
break;
}
} // 至此，v的所有邻居都已访问结束, 将v标记为VISITED
v.setFStamp(clock++); //将v标记为VISITED 返回null；然后回溯。
return null; //然后回溯。
}
}
全部评论 (0)
