原文: 算法起步之深度优先搜索

       说完广度优先搜索后，我们来看图的另一种遍历形式，深度优先搜索算法，深度优先总是对刚发现的节点的出阿发边进行探索，直到该节点的所有出发边都被发现为止。一旦所有的出发边都被发现，搜索就回溯到前驱结点，来搜索前驱结点的出发边。反复进行直到全部遍历。我们用递归跟栈两种方式进行实现，其实归根到底递归也是栈实现的。

       递归实现：

 

public class DFS {
	
	private boolean[] visited;
	public void dfs(int[][]map){
		visited=new boolean[map.length];
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				core(map, i);
			}
		}
	}

	public void core(int[][]map,int node){
		System.out.println(node);
		visited[node]=true;
		for (int i = 0; i < visited.length; i++) {
			if (map[node][i]==1&&!visited[i]) {
				core(map,i);
			}
		}
		}
}

       栈实现：

private LinkedList list=new LinkedList();
	private boolean[] visited;
	public void dfs(int[][] map){
		visited=new boolean[map.length];
		for (int i = 0; i < visited.length; i++) {
			if (!visited[i]) {
				list.addLast(i);
				while (!list.isEmpty()) {
					int now=(Integer) list.getLast();
					visited[now]=true;
					System.out.println(now);
					int link=getlink(map, now);
					if (link!=-1) {
						list.add(link);
					}else {
						list.removeLast();
					}
				}
			}
			
			
			
		}
		
	}
	public int getlink(int[][]map,int node){
		for (int i = 0; i < map.length; i++) {
			if (map[node][i]==1&&!visited[node]) {
				return i;
			}
		}
		return -1;
	}