本段落提供了一个用于执行深度优先搜索（DFS）的Java代码模板，专注于有向图的应用场景。该模板包含了递归实现方式，并附带了基本的数据结构和标记机制以避免无限循环。它适用于解决各种涉及图论的问题，如路径查找、连通性分析等。
以下是关于有向图深度优先遍历算法的模板代码：
```java
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) {
if (v.getStatus() != UNDISCOVERED)
return null; // 跳过已访问过的顶点，适用于非连通图的情况
v.setDStamp(clock++);
v.setStatus(DISCOVERED);
visit(v, info); // 访问当前节点
for (Iterator it = v.outEdges(); it.hasNext();) {
Edge e = (Edge)it.getNext();
Vertex u = (Vertex)e.getVPosInV(1).getElem();
switch(u.getStatus()) {
case UNDISCOVERED :
// 如果u尚未被发现，则将边e归类为树边，并从顶点u继续进行深度优先搜索
e.setType(TREE);
traverse(u, info);
break;
case DISCOVERED :
// 若u已经被发现，但对其访问尚未结束，则将e归类为后向跨边
e.setType(BACKWARD);
break;
default :
if (u.getDStamp() < v.getDStamp()) {
// 如果相对于v顶点而言，u被发现得更早，则将e归类为横跨边
e.setType(CROSS);
} else {
// 否则将其分类为前向跨边
e.setType(FORWARD);
}
}
}
v.setFStamp(clock++);
v.setStatus(VISITED);
return null;
}
}
```
这段代码定义了一个抽象类DFS，该类继承自GraphTraverse。它提供了一个名为traverse的方法用于执行深度优先搜索算法，并根据顶点的状态更新边的类型（树边、后向跨边、横跨边或前向跨边）。
5星
