「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。

岛屿问题

200. 岛屿数量

输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1

运用深度优先搜索，当发现一个陆地1时，深度搜索周围所有的1，并将访问过的陆地1替换为2。

  1. var numIslands = function(grid) {
  2.   if(grid.length===0 || grid[0].length===0) return 0;
  3.   let count=0;
  4.   for(let i=0;i<grid.length;i++){
  5.       for(let j=0;j<grid[0].length;j++){
  6.         if(grid[i][j]==='1'){
  7.             dfs(grid,i,j)
  8.             count++;
  9.         }
  10.       }
  11.   }
  12.   return count;
  13. };
  15. var dfs = function(grid,i,j){
  16.    if(!(i>=0 && j>=0 && i< grid.length && j< grid[0].length)) return;
  17.    if(grid[i][j]!=='1') return;
  19.    grid[i][j]='2'
  20.    dfs(grid,i-1,j)
  21.    dfs(grid,i+1,j)
  22.    dfs(grid,i,j-1)
  23.    dfs(grid,i,j+1)
  24. }

695. 岛屿的最大面积

  1. /**
  2.  * @param {number[][]} grid
  3.  * @return {number}
  4.  */
  5. var maxAreaOfIsland = function(grid) {
  6.     const m=grid.length
  7.     const n = grid[0].length
  8.     let result=0;
  9.     for(let i =0;i<m;i++){
  10.         for(let j =0;j<n;j++){
  11.             if(grid[i][j]){
  12.                 const ans=dfs(i,j,grid)
  13.                 result=Math.max(ans,result)
  14.             }
  15.         }
  16.     }
  17.     function dfs(i,j,graph){
  18.         if(!(i>=0 && j>=0 && i<graph.length && j<graph[0].length)) return 0 ;
  19.         if(graph[i][j]!==1) return 0 
  20.         graph[i][j]=2
  21.         return dfs(i-1,j,graph)+dfs(i+1,j,graph)+dfs(i,j-1,graph)+dfs(i,j+1,graph)+1
  22.         //相加得到岛屿的面积，就像后序遍历求二叉树树高一样
  23.      }
  24.      return result;
  25. };

130. 被围绕的区域

  1. /**
  2.  * @param {character[][]} board
  3.  * @return {void} Do not return anything, modify board in-place instead.
  4.  */
  5. var solve = function(board) {
  6.     const n=board.length;
  7.     const m=board[0].length; //m,n可能不相等
  8.      for(let i=0;i<n;i++){
  9.         dfs(i,0,board)
  10.         dfs(i,m-1,board)
  11.      }
  12.      for(let j=1;j<m;j++){
  13.         dfs(0,j,board)
  14.         dfs(n-1,j,board)
  15.      }
  16.      for(let i=0;i<n;i++){
  17.         for(let j=0;j<m;j++){
  18.             if(board[i][j]==='A'){
  19.                 board[i][j]='O'
  20.             }else if(board[i][j]==='O'){
  21.                 board[i][j]='X'
  22.             }
  23.         }      
  24.      }
  25.      function dfs(i,j,graph){
  26.         if(!(i>=0 && j>=0 && i<graph.length && j<graph[0].length)) return;
  27.         if(graph[i][j]!=='O') return
  28.         graph[i][j]='A'
  29.         dfs(i-1,j,graph)
  30.         dfs(i+1,j,graph)
  31.         dfs(i,j-1,graph)
  32.         dfs(i,j+1,graph)
  33.      }
  34.      return board;
  35. };

图的遍历

其实就是多叉树的遍历，不过可能会有环，所以需要加vistied标记

797. 所有可能的路径

  1. /**
  2.  * @param {number[][]} graph
  3.  * @return {number[][]}
  4.  */
  5. var allPathsSourceTarget = function(graph) {
  6.    let result=[],path=[]
  7.    function backtracking(cur,graph){      
  8.       path.push(cur)  //与回溯的区别，把path.push放在了循环外，使根节点能被添加到path中
  9.       if(cur===graph.length-1){
  10.         result.push([...path])
  11.         path.pop() //这里记得pop
  12.         return;
  13.       }
  14.       for(let i of graph[cur]){         
  15.          backtracking(i,graph)        
  16.       } 
  17.       path.pop()
  18.    }
  19.    backtracking(0,graph);
  20.    return result;
  21. };

207. 课程表

  1. /**
  2.  * @param {number} numCourses
  3.  * @param {number[][]} prerequisites
  4.  * @return {boolean}
  5.  */
  6. var canFinish = function(numCourses, prerequisites) {
  7.   //如果有环则无法完成
  8.   //根据prerequisites生成邻接表，然后遍历看有没有坏
  9.   function getAdjvex(prerequisites){
  10.      let list=Array.from(Array(numCourses),()=>[])
  11.      for(let [k,v] of prerequisites){
  12.          list[v].push(k)
  13.      }
  14.      return list
  15.   }
  16.   let graph=getAdjvex(prerequisites);
  17.   function backtracking(cur,graph){
  18.      if(path.indexOf(cur)>-1){ //说明有环
  19.          result=false;
  20.          return;
  21.      }
  22.      if(visited[cur]) return; 
  23.     //例如a,b同时都指向了c，为了节约遍历，如果c之前已被访问过，说明c之后的节点已被递归处理，return
  24.      visited[cur]=true;
  25.      path.push(cur)
  26.      for(let i of graph[cur]){
  27.        backtracking(i,graph)
  28.      }
  29.      path.pop();
  30.   }
  31.   let result = true;
  32.   let visited=Array(numCourses).fill(false); //已访问节点
  33.   let path=[] //当前访问路径
  34.   for(let i=0;i<numCourses;i++){ 
  35.     //图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。
  36.        backtracking(i,graph)
  37.   }
  38.   return result;
  39. };

210. 课程表 II

两种方法：1、DFS拓扑排序
2、BFS拓扑排序

  1. //DFS拓扑排序,在课程表1的基础上，增加了学习顺序数组，运用后序遍历的reverse结果。
  2. var findOrder = function(numCourses, prerequisites) {
  3.   function getAdjvex(prerequisites){
  4.      let list=Array.from(Array(numCourses),()=>[])
  5.      for(let [k,v] of prerequisites){
  6.          list[v].push(k)
  7.      }
  8.      return list
  9.   }
  10.   let graph=getAdjvex(prerequisites);
  11.   function backtracking(cur,graph){
  12.      if(path.indexOf(cur)>-1){
  13.          isCircle=true;
  14.          return;
  15.      }
  16.      if(visited[cur]) return;
  17.      visited[cur]=true;
  18.      path.push(cur)
  19.      for(let i of graph[cur]){
  20.        backtracking(i,graph)
  21.      }
  22.      result.push(cur);// 学习顺序
  23.      path.pop();
  24.   }
  25.   let isCircle = false;
  26.   let visited=Array(numCourses).fill(false); //已访问节点
  27.   let path=[] //当前访问路径
  28.   let result=[]
  29.   for(let i=0;i<numCourses;i++){
  30.        backtracking(i,graph)
  31.   }
  32.   return isCircle?[]:result.reverse();
  33. };
  1. //BFS拓扑排序
  2. //记录每个节点的入度
  3. //一层层往下，如果入度为0则加入结果集。

并查集

https://labuladong.gitee.io/algo/2/20/51/
并查集是来解决图的连通性问题

  • Union — 连接两个节点
  • Find — 查找所属的连通分量

所以，并查集主要就是实现以下接口：

  1. class UF {
  2.     /* 将 p 和 q 连接 */
  3.     public void union(int p, int q);
  4.     /* 判断 p 和 q 是否连通 */
  5.     public boolean connected(int p, int q);
  6.     /* 返回图中有多少个连通分量 */
  7.     public int count();
  9.     /* 返回当前节点的根节点 */
  10.     private int find(int x);
  11. }

如何表示节点与节点之间的连通性关系呢？？

  • 如果 p 和 q 连通，则它们有相同的根节点

用数组 parent[] 来表示这种关系。

547. 省份数量

  1. /**
  2.  * @param {number[][]} isConnected
  3.  * @return {number}
  4.  */
  5. var findCircleNum = function(isConnected) {
  6.     const uf=new UF(isConnected.length)
  7.     for(let i=0;i<isConnected.length;i++){
  8.         // for(let j=0;j<isConnected[i].length;j++){
  9.         for(let j=0;j<i;j++){ //因为对称性
  10.             if(isConnected[i][j]){
  11.               uf.join(i,j)
  12.             }
  13.         }
  14.     }
  15.     return uf.getCount();
  16. };
  18. class UF{
  19.     constructor(count){
  20.        this.count=count;
  21.        this.parent=Array.from(Array(count),(x,i)=> i)
  22.     }
  23.     join(a,b){
  24.       const rootA=this.find(a);
  25.       const rootB=this.find(b);
  26.       if(rootA ===rootB) return
  27.       this.parent[rootA]=rootB;
  28.       this.count--;
  29.     }
  30.     find(x){
  31.        while(this.parent[x]!==x){
  32.            this.parent[x]=this.parent[this.parent[x]]// 压缩层高
  33.            x=this.parent[x]
  34.        }
  35.        return x;
  36.     }
  37.     getCount(){
  38.         return this.count;
  39.     }
  40. }

128. 最长连续序列

最先想到sort排序然后动态规划求最长连续序列，但是由于时间复杂度O(n)的限制，该方法pass
1、使用并查集，建立相邻数字之间的联系，然后得到连通量；但其实n+1/n-1已经是隐形的联系了，所以不用并查集方法了。
2、使用map记录右边界，用空间换时间

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var longestConsecutive = function(nums) {
  6.   //时间复杂度为 O(n)
  7.   let map=new Map();
  8.   let result=0;
  9.   for(let num of nums){
  10.       map.set(num,num)
  11.   }
  12.   for(let num of nums){
  13.       if(!map.get(num-1)){ //当还有n-1时就不处理，因为处理到n-1时会包含到n
  14.           let right=num
  15.           while(map.get(right+1)!==undefined){
  16.              right=map.get(right+1)
  17.           }
  18.           map.set(num,right);
  19.           result=Math.max(result,right-num+1);
  20.       }
  21.   }
  22.   return result;
  23. };