深度优先算法

转载自：http://blog.csdn.net/u014394715/article/details/51192293

深度优先算法

定义

wiki上的解释：

深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

当然看到上面这句话的时候，我并没有理解什么到底是DFS，因此又看了很多人的说话，有了下面一段话：  DFS的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底。  DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。

---

深度与广度的比较

我们搜索一个图是按照树的层次来搜索的。

我们假设一个节点衍生出来的相邻节点平均的个数是N个，那么当起点开始搜索的时候，队列有一个节点，当起点拿出来后，把它相邻的节点放进去，那么队列就有N个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了N2，你可以想想，一旦N是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。

于是广度优先搜索的缺点出来了：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。

那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想，广度优先能够找到最短路径，那深度优先能否找到呢？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？

于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。

数字为搜索顺序

代码（转）

public class DFSTest { // 存储节点信息 private char[] vertices; // 存储边信息（邻接矩阵） private int[][] arcs; // 图的节点数 private int vexnum; // 记录节点是否已被遍历 private boolean[] visited; // 初始化 public DFSTest(int n) { vexnum = n; vertices = new char[n]; arcs = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { arcs[i][j] = 0; } } } // 添加边(无向图) public void addEdge(int i, int j) { // 边的头尾不能为同一节点 if (i == j)return; arcs[i][j] = 1; arcs[j][i] = 1; } // 设置节点集 public void setVertices(char[] vertices) { this.vertices = vertices; } // 设置节点访问标记 public void setVisited(boolean[] visited) { this.visited = visited; } // 打印遍历节点 public void visit(int i){ System.out.print(vertices[i] + " "); } // 从第i个节点开始深度优先遍历 private void traverse(int i){ // 标记第i个节点已遍历 visited[i] = true; // 打印当前遍历的节点 visit(i); // 遍历邻接矩阵中第i个节点的直接联通关系 for(int j=0;j<vexnum;j++){ // 目标节点与当前节点直接联通，并且该节点还没有被访问，递归 if(arcs[i][j]==1 && visited[j]==false){ traverse(j); } } } // 图的深度优先遍历（递归） public void DFSTraverse(){ // 初始化节点遍历标记 for (int i = 0; i < vexnum; i++) { visited[i] = false; } // 从没有被遍历的节点开始深度遍历 for(int i=0;i<vexnum;i++){ if(visited[i]==false){ // 若是连通图，只会执行一次 traverse(i); } } } // 图的深度优先遍历（非递归） public void DFSTraverse2(){ // 初始化节点遍历标记 for (int i = 0; i < vexnum; i++) { visited[i] = false; } Stack<Integer> s = new Stack<Integer>(); for(int i=0;i<vexnum;i++){ if(!visited[i]){ //连通子图起始节点 s.add(i); do{ // 出栈 int curr = s.pop(); // 如果该节点还没有被遍历，则遍历该节点并将子节点入栈 if(visited[curr]==false){ // 遍历并打印 visit(curr); visited[curr] = true; // 没遍历的子节点入栈 for(int j=vexnum-1; j>=0 ; j-- ){ if(arcs[curr][j]==1 && visited[j]==false){ s.add(j); } } } }while(!s.isEmpty()); } } } public static void main(String[] args) { DFSTest g = new DFSTest(9); char[] vertices = {'A','B','C','D','E','F','G','H','I'}; g.setVertices(vertices); g.addEdge(0, 1); g.addEdge(0, 5); g.addEdge(1, 0); g.addEdge(1, 2); g.addEdge(1, 6); g.addEdge(1, 8); g.addEdge(2, 1); g.addEdge(2, 3); g.addEdge(2, 8); g.addEdge(3, 2); g.addEdge(3, 4); g.addEdge(3, 6); g.addEdge(3, 7); g.addEdge(3, 8); g.addEdge(4, 3); g.addEdge(4, 5); g.addEdge(4, 7); g.addEdge(5, 0); g.addEdge(5, 4); g.addEdge(5, 6); g.addEdge(6, 1); g.addEdge(6, 3); g.addEdge(6, 5); g.addEdge(6, 7); g.addEdge(7, 3); g.addEdge(7, 4); g.addEdge(7, 6); g.addEdge(8, 1); g.addEdge(8, 2); g.addEdge(8, 3); System.out.print("深度优先遍历（递归）："); g.DFSTraverse(); System.out.println(); System.out.print("深度优先遍历（非递归）："); g.DFSTraverse2(); } } ---------- Output： 深度优先遍历（递归）：A B C D E F G H I 深度优先遍历（非递归）：A B C D E F G H I 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170

---

博客中有些内容引自：  深度优先搜索(DFS)理解DFS概念上很清晰