图论基础算法/DFS+BFS+Trie树

八、图论

8.1深度优先搜索

• 和树类似，只不过这里需要优化，因为是多对多，对访问的节点加上标记防止重复访问，（下面BFS的题目腐烂的橘子因为有权重值，也就判断是一次污染还是二次三次…污染，所以不能这么简单标记，不可以DFS）

• 力扣200

  class Solution {
      public int numIslands(char[][] grid) {
          int res = 0;
          int row = grid.length;
          for (int i = 0; i < row; i++) {
              for (int j = 0; j < grid[i].length; j++) {
                  if (grid[i][j] == '1') {
                      dfs(grid, i, j);
                      res++;
                  }
              }
          }
          return res;
      }
  
      public void dfs(char[][] grid, int x, int y) {
          if (x < 0 || y < 0 || y >= grid[0].length || x >= grid.length || grid[x][y] != '1') {
              return;
          }
          grid[x][y] = '2';
          dfs(grid, x, y - 1);
          dfs(grid, x, y + 1);
          dfs(grid, x - 1, y);
          dfs(grid, x + 1, y);
      }
  }
  

  就是对访问过的陆地变为2（碰到不会重复访问），然后进行DFS，如果是最后多条路径碰到水或者四周就说明就是一块岛屿。然后主循环继续寻找为1的陆地，然后进行dfs，循环往复

8.2广度优先搜素

8.2.1拓扑排序

1. 首先初始化一个入度表（数组）、一个邻接表（二位数组）、一个队列（用来拓扑排序的构建）
2. 遍历队列，删除首元素，根据首元素的删除，动态减少入度表的值（只需要更改，首元素指向的几条点，因为只改了这几个点的入度），直到遍历队列为空。

• 注意拓扑排序使用于有向无环图，所以可以用来判断有向无环图，例如力扣207，思路和上面一致

  class Node {
      public Node[] son = new Node[26];
      boolean end; 
  }
  
  class Trie {
      privare Node = root;
  
      public Trie() {
          root = new Node();
      }
      
      public void insert(String word) {
          Mode cur = root;
          for (char c : word.toCharArray()) {
              c -= 'a';
              if (cur.son[c] == null) { // 插入值就是有子节点
                  cur.son[c] = new Node();
              }
              cur = cur.son[c];
          }
          cur.end = True;  // 防止遍历到最后一个空节点，来一个终止标记，也代表一共单词的截止
      }
      
      public boolean search(String word) {
          return find(word) == 2;  // 加入的单词末尾会有End=True
      }
      
      public boolean startsWith(String prefix) {
          return find(prefix) != 0;
      }
  
      private int find(String word) {
          Node cur = root;
          for (char c : word.toCharArray()) {
              c -= 'a';
              if (cur.son[c] == null) {
                  return 0;
              }
              cur = cur.son[c];
          }
          return cur.end ? 2 : 1
      }
  }
  

8.2.2多源bfs

• 就是从不同点进行bfs，就像是一个区域，有几个污染的地方，那么肯定先污染附近的地方，多元bfs就这样

• 例如力扣994：腐烂的橘子

  1. 先获得新鲜橘子数量和腐烂橘子的位置

  2. 去遍历腐烂橘子的位置，先污染周围的新鲜橘子，然后删除旧的污染橘子，因为周围的被污染过了，把新的污染橘子加进去，就是二次污染了。注意要区分一次污染和二次污染，这里隔离了存放位置的数组

     class Solution {
         private static int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
     
         // 多源BFS，由每个坏橘子只感染周围一圈的橘子，防止DFS那样多次判断修改同一个地方
         public int orangesRotting(int[][] grid) {
             int m = grid.length;
             int n = grid[0].length;
             List<int[]> bad = new ArrayList<>();
             int fresh = 0;
             // 先获取新鲜橘子数量，和坏橘子的位置
             for (int i = 0; i < m; i++) {
                 for (int j = 0; j < n; j++) {
                     if (grid[i][j] == 1) {
                         fresh++;
                     } else if (grid[i][j] == 2) {
                         bad.add(new int[]{i, j});
                     }
                 }
             }
     
             int ans = 0;
             while (!bad.isEmpty() && fresh > 0) {
                 ans++;
                 List<int[]> tep = bad;
                 bad = new ArrayList<>();
                 for (int[] a : tep) {
                     for (int[] d : DIRECTIONS) {
                         int i = a[0] + d[0];
                         int j = a[1] + d[1];
                         if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) {
                             fresh--;
                             grid[i][j] = 2;
                             bad.add(new int[]{i, j});
                         }
                     }
                 }
             }
             return fresh > 0 ? -1 : ans;
         }
     }
     

• Q&A

  1. 为什么不从新鲜橘子走，而是从腐烂橘子走

     如果从新鲜橘子走的话，肯定是遍历腐烂橘子的位置，这个时候如果很远的地方才有腐烂橘子，那么要隔很久才能污染，这里会有更加复杂的逻辑计算，所以不采用

  2. 为什么不用DFS？

     因为DFS是一条路走到死，因为此题有权重值，可能会导致一个地方被重复修改，需要加判断来确定留哪一次修改。

  3. 为什么用迭代不用递归

     和树的BFS同理，用递归首先更为方便，因为就是按照逻辑层序遍历，不是递归栈那样。用递归的BFS其实有点大材小用。

8.3Trim树

1. 其实就是字典树，和正常的树不一样，节点其实存的是长度为26的数组，每一个值存的是下一个字母的数组的地址。还需要加一个遍历来表明是不是最后一个字母，比如apple是一个单词，在字典树，是一个数组，其中有一条这样的指向a->p->p->l->e是这样，我需要直到遍历到e这个数组直到是有一个单词的结尾，那么就加一个变量表明这里可以是一个结尾。

   逻辑如下

   class Node {
       public Node[] son = new Node[26];
       boolean end; 
   }
   
   class Trie {
       private Node root;
   
       public Trie() {
           root = new Node();
       }
       
       public void insert(String word) {
           Node cur = root;
           for (char c : word.toCharArray()) {
               c -= 'a';
               if (cur.son[c] == null) { // 插入值就是有子节点
                   cur.son[c] = new Node();
               }
               cur = cur.son[c];
           }
           cur.end = true;  // 防止遍历到最后一个空节点，来一个终止标记，也代表一共单词的截止
       }
       
       public boolean search(String word) {
           return find(word) == 2;  // 加入的单词末尾会有End=True
       }
       
       public boolean startsWith(String prefix) {
           return find(prefix) != 0;
       }
   
       private int find(String word) {
           Node cur = root;
           for (char c : word.toCharArray()) {
               c -= 'a';
               if (cur.son[c] == null) {
                   return 0;
               }
               cur = cur.son[c];
           }
           return cur.end ? 2 : 1;
       }
   }