深度优先搜索算法(DFS)
标签（空格分隔）： algorithm
1.深度优先搜索算法(Deep Fisrt Search)
- 深度优先搜索顾名思义，就是要有深度，而不是像BFS那样把自己旁边的节点作为第一个优先级的去搜索。
- 而是首先把自己存起来，然后随机找一个自己的邻接节点，在以这个邻接节点为起始节点去搜索图中与之相邻的节点。一直搜索下去，递归下去，那么什么时候，停止呢？（递归的出口）
- 对于一个节点什么时候会停止对这个节点及其邻接点的访问呢？
- 1.如果这个点的没有邻接点，那么返回上一个节点，继续这个节点的其他节点搜索
- 2.如果这个节点的邻接点都已经搜索完，那么需要返回上一个节点继续搜索。
- 上面的描述有一种节点一个个先进入，然后一个个再出来，而且是先进去的后出来或者后进来的先出去,只有遍历完下一节点，才会遍历上一个节点。
- 所以这个特征刚好符合栈的特征，所以可以使用栈来实现这个算法。
- 伪代码
void traveralGraph(){
初始化标志hashmap
for node in G: // 对图中的每一个节点
如果没有被访问：hashmap[node] == false
执行DFS DFS(G,node,hashmap)
}
void DFS(G,node,hashmap){
// 递归的出口
如果节点被访问了：if hashmap[node] == true:
返回： return
1.访问节点：visited(node)
2.标志节点已被访问:hashmap[node] = true
3.获取node节点的旁边，邻接节点集合:adjlist = getadjList(node)
for adjNode : adjlist: 对每一个邻接点，执行
1).如果邻接点没有被访问：hashmap[adjNode] != true
2).以这个节点开始，进行DFS遍历 :DFS(G,adjNode,hashmap)
}
}
- 从遍历的过程来看，对于整个图的遍历是，以每一个节点为起始节点开始DFS搜索的，如果一次调用DFS可以把图中所有的节点都遍历了，那么也不需要for 循环对图中的每个节点在调用DFS
- 关键点在DFS函数中的for 循环，这个for 循环表示以当前节点的某个邻接点在进行搜索，实际为把这个节点压栈，然后在访问邻接点的邻接点，一直这么下去。看DFS退出的条件
- 2).这个节点没有邻接点，那么for循环不会执行：以这个节点的遍历完成
- 3).这个节点有邻接点，for 循环执行,且for 循环执行完了：以这个节点的遍历完成，需要返回上一层，继续遍历上个节点的邻接节点
- 能看出只要2),3)执行就会访问到节点，访问节点的数就会增加，为访问的就会减少，最终所有节点都会被访问
- DFS函数中的递归调用：for DFS的执行返回意味着什么？
- 假设现在有图
A --- B --- C
|
D
|
E
- 我们从A节点开始出发使用DFS来遍历这个图
- 首先会访问A节点 -> 访问B节点-> 访问C节点-> 没有邻接点，C访问完成返回 -> 继续访问B的邻接点D -> 访问节点E -> E访问完成 -> 返回到D -> D的邻接点E完成访问返回到B节点 -> B邻接点CD都访问完返回A节点-> A邻接点B 完成访问 -> 完成以A节点开始的遍历
| | | | | C | | | | D | | | | E | | |
| | --> | B | -> | B | -> | B | | B | | B | | B | |B|
| A | | A | | A | | A | | A | | A | | A | |A|
—————
DFS(A) ->for
DFS(B) -> for n in (D,C)
DFS(C)
DFS(D) DFS(C)返回
DFS(D) for
DFS(E)
DFS(E)返回
DFS(D)返回
DFS(B)返回
DFS(A)返回
- 伪代码
public class DFSMethod {
public static void main(String[] args){
G = new Graph();
hashmap = new hashmap();
for node in G:
if hashmap[node] == false:
DFS(G,node,hashmap);// 表示从0 节点开始遍历
}
public static void BFS(G,node,hashmap) {
//1.已经认为是在队列当中，说明已经要被访问了，所以这么标志
visitedMap.put(node, true);
//2.访问
visited(node);
// 3.获取相邻的节点
ArrayList<Node> adjNodeList = G.getAdjectList(q);
// 4.开始以邻接点为七点执行DFS搜索
for(int i = 0; i < adjNodeList.size() ; ++i) {
node = adjNodelist.get(i)
/**没有被访问过，则以这个节点开始执行DFS搜索*/
if (visitedMap[node] == false) { // 没有被访问过
DFS(g,node,hashmap);
}// end if
}//end for
}
public static void visited(Node s) {
// 这里只是简单的打印一下，可进行性统计、计数等操作
System.out.println(s);
}
}
2 图联通量的遍历
2.1 问题描述
- 岛的最大面积
- 假设有一块地，地中有两种地方，一种是岛：人可以到达，另一种是有水的地方，人不可以到达。每个岛只能从上下左右到达。
- 抽象成数学问题就是，一个二维矩阵表示一块地，岛用1表示，水用0 表示，岛和岛之间如果在垂直或者水平方向相邻，则认为这两个岛是可以组成一个大岛，现在是要问，这块地上由小岛组成多个大岛，那么最大的岛的面积是多少呢？
- 抽象数据结构问题：问这个图中有多少个连通分量，在这些连通分量中，哪个连通分量的节点数最多
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1*,0, 1*,0,0],
[0,1,0,0,1,1,0,0,1*,1*,1*,0,0],
[0,0,0,0,0,0,0,0,0,0,1*,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
上述中有个连通分量（带*的1），大小为6
- 解答的思路是：通过BFS或者DFS遍历整个图，计算出需要调用BFS或者DFS过程当中一次性的访问了多少个节点，把访问节点个数的最大值记录下来。
- 实际为visited函数的使用，在对图的遍历中以某个节点开始遍历时，这个节点的所有邻接节点，都被访问完时，visited函数访问了多少次。
- 下次以另一节点开始访问时，重新记录，另一个连通分量的中节点个数
/***
* x,y 坐标的相邻坐标
* (x-1,y-1)---(x-1,y)----(x,y-1)
* (x , y-1)---(x , y)----(x,y+1)
* (x+1,y-1)---(x+1,y)----(x+1,y+1)
*/
public static int visitedCount = 0;
public static int maxAreaOfIsland(int[][] grid) {
//访问标志
HashMap<String,Boolean> visitedMap = new HashMap<String,Boolean>();
int count = 0;
for(int x =0; x < grid.length; ++x) {
for(int y = 0; y < grid[0].length; ++y) {
if(grid[x][y] == 0)// 跳过非连通节点
continue;
String xykey = x + ":" + y;
if(visitedMap.containsKey(xykey) == false) {
DFS(grid,visitedMap,x,y);// 把连通的岛遍历一下，并标志下，visitedCount记录这个连通分量节点数
count = count > visitedCount ? count : visitedCount;
visitedCount = 0;// 下一个连通分量遍历
}
}
}
return count;
}
public static void DFS(int[][] grid,HashMap<String,Boolean> visitedMap,int startx,int starty) {
NodeValue e = new NodeValue(startx, starty);
//访问标志
visitedMap.put(startx + ":" + starty, true);
visited(e);
/*获取邻接点集合*/
ArrayList<NodeValue> adjlist = getAdjList(grid,e);
// 邻接点调用DFS
for(int i = 0 ;i < adjlist.size(); ++i) {
e = adjlist.get(i);
String ekey = e.x +":" + e.y;
if(visitedMap.containsKey(ekey) == false) {
DFS(grid,visitedMap,e.x,e.y);
}
}
}
private static void visited(NodeValue e) {
visitedCount ++;// 访问到的节点数增加，计数功能
}
/**寻找其相邻节点的函数*/
public static ArrayList<NodeValue> getAdjList(int[][] grid,NodeValue e) {
ArrayList<NodeValue> adjlist = new ArrayList<NodeValue>();
int xlen = grid.length;
int ylen = grid[0].length;
if(e.x - 1 >=0 ) { // 上面(x-1,y)
if (grid[e.x -1][e.y] == 1) {
adjlist.add(new NodeValue(e.x - 1,e.y));
}
}
if(e.y - 1 >=0 ) { //左面(x,y-1)
if (grid[e.x][e.y - 1 ] == 1) {
adjlist.add(new NodeValue(e.x,e.y - 1 ));
}
}
if(e.x + 1 < xlen ) { // 下面 (x+1,y)
if (grid[e.x + 1][e.y] == 1) {
adjlist.add(new NodeValue(e.x + 1,e.y));
}
}
if(e.y + 1 < ylen ) { // 右面(x,y+1)
if (grid[e.x ][e.y + 1] == 1) {
adjlist.add(new NodeValue(e.x,e.y + 1));
}
}
return adjlist;
}
/**存储下x,y的坐标*/
static class NodeValue{
public int x, y;
public NodeValue(int x,int y){
this.x = x;
this.y = y;
}
}
- 看着上面的题目是不是和BFS当中介绍的求岛的个数题目非常类似？
- 没错就是很类似，只是使用了DFS和visited函数来实现这个问题
- 其实这个问题使用BFS也能够解决，因为这个题的目的是遍历节点，那么DFS和BFS都是可以达到这个目的的
- 这个题目中每个节点的权重，是1，如果把这个权重1换成其他的数字，或者求其他在遍历过程中有意义的数，都是可以通过DFS&BFS来实现的。
- 大多数的图的搜索(只读算法)都是使用DFS&BFS，配合visited函数的使用，就可以满足搜索的要求，如果需要在搜索过程你当中修改图节点的原本属性，那么就需要使用回溯算法，下次将要介绍。
- 深度优先搜索，是函数的递归调用，之前介绍过，大多数的递归逻辑都是可以使用栈来实现的，下次将介绍如何使用栈来实现DFS，那么图的遍历就可以认为是队列和栈这两种数据结构的应用了。
3.参考内容：
- 1.算法导论第22章基本图算法-深度优先搜索
- 2.leetcode 695题目Max Area of Island
