深度优先搜索算法(DFS)

深度优先搜索算法(BFS)

标签（空格分隔）： algorithm

---

1.深度优先搜索算法(Breath 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