/* * （有向）图的深度优先遍历算法模板 */ 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();) {//检查与顶点v Edge e = (Edge)it.getNext();//通过边e = (v, u) Vertex u = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u switch (u.getStatus()) {//根据u当前的不同状态，分别做相应处理 case UNDISCOVERED ://若u尚未被发现，则 e.setType(TREE);//e被归类为“树边” traverse(u, info);//从u出发，继续做深度优先查找 break; case DISCOVERED ://若u已经被发现，但对其访问尚未结束，则 e.setType(BACKWARD);//将e归类为“后向跨边” break; default ://VISITED，即对u的访问已经结束 if (u.getDStamp() < v.getDStamp())//若相对于v，u被发现得更早，则 e.setType(CROSS);//将e归类为“横跨边” else//否则 e.setType(FORWARD);//将e归类为“前向跨边” break; } }//至此，v的所有邻居都已访问结束，故 v.setFStamp(clock++); v.setStatus(VISITED);//将v标记为VISITED return null;//然后回溯 } }

数据结构：图的深度优先遍历

【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的有向图上访问全部结点的操作。 【基本要求】 以邻接表为存储结构，实现创建图、销毁图、查找顶点、获取顶点值、顶点赋值、获得第一邻接点、获得下一邻接点、插入顶点、删除顶点、插入弧、删除弧、深度优先搜索遍历、广深度优先搜索遍历等操作 注： 1.系统设计 2.系统主界面演示系统设计：包含欢迎菜单为新建表、打开文件、退出程序 3.操作界面设计：创建图、销毁图、查找顶点、获取顶点值、顶点赋值、获得第一邻接点、获得下一邻接点、插入顶点、删除顶点、插入弧、删除弧、深度优先搜索遍历、广深度优先搜索遍历等13个 3.代码中有三个头文件，1个主函数；共700行代码，是一个完整的系统设计 4.代码进行了多次调试与运行，绝对可以编译并执行。 5.软件用VS2019打开

图遍历的演示 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 【基本要求】 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 注： 1.代码共182行。 2.代码经过多次编译运行，无错误。

vc6编译器编译，C语言写的代码，老鼠走迷宫，用广度优先的寻找最短的路径算法，遍历全部路径使用的是深度算法。完整代码可直接下载调试运行。

随机迷宫生成及最短路径寻找（QT实现可视化）（深度优先遍历）

包括两程序，一个是用邻接矩阵存储图实现深度优先遍历和广度优先遍历，一个是用临街链表存储实现深度优先遍历和广度优先遍历，均调试无误

c++-深度优先遍历的递归实现版本

用R语言实现用深度优先搜索的方法遍历图中所有的点，带源代码，复制粘贴即可运行，每个步骤带有详细注释，方便深层次理解

该资源为迷宫随机生成程序，用Eclipse平台开发的，采用了深度优先遍历算法。迷宫行数列数在界面输入；入口为定点（左上角）；有两个出口，在右边界和下边界随机选择。