深度优先搜索与探索迷宫十分相似,探索迷宫而不迷路的一种古老方法叫做Tremaux搜索。要探索迷宫中的所有通道,我们需要:
①选择一条没有标记过的通道,在你走过的路上铺一条绳子;
②标记所有你第一次路过的路口和通道;
③当来到一个标记过的路口时回退到上个路口;
④当回退到的路口已经没有可走的通道时继续回退。
public class DepthFirstSearch { private boolean[] marked; private int count; public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()];//G.V()获得图的顶点数 dfs(G, s); } private void dfs(Graph G, int v) { marked[v] = true; count++; for(int w : G.adj(v)) {//G.adj(v)获得与v相邻的顶点 if(!marked[w]) { dfs(G, w); } } } }