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

发布于:2024-12-23 ⋅ 阅读:(13) ⋅ 点赞:(0)

八、图论

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;
        }
    }