课程名称：JavaScript版数据结构与算法
课程章节：第9章 数据结构之“图”
主讲老师：lewis

课程内容：

今天学习的内容包括：
9-4 LeetCode：417. 太平洋大西洋水流问题——利用图的深度优先遍历循环即可。
9-5 LeetCode：133. 克隆图——拷贝所有的节点和边。
9-6 图-章节总结——网络结构的抽象模型，由边连接。
9-7 【勤于思考，夯实学习成果】阶段思考题——生活中的一些应用。

课程收获：

417. 太平洋大西洋水流问题

1、新建两个矩阵，分别记录能流到两个大洋的坐标，在这里使用图进行标记，分别为flow1、flow2。
2、从海岸线开始，进行深度优先遍历，遍历中将相邻的满足的值填充到flow1、flow2。
3、遍历flow1、flow2,找出能流到两个大洋的坐标。

const flow1 = Array.from({length: m}, () => new Array(n).fill(false))
循环中拿到对用的上下左右坐标进行遍历递归处理
 [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]].forEach()
 满足条件调用递归方法
 // 保证在矩阵中
 nr >= 0 && nr < m &&
 nc >= 0 && nc < n &&
 // 防止死循环
 !flow[nr][nc] &&
 // 保证逆流而上
 heights[nr][nc] >= heights[r][c]

133. 克隆图

1、深度或广度优先遍历所有节点。
2、拷贝所有节点，储存起来。
3、将拷贝的节点，按照原图的链接方法进行连接。

const dfs = (n) => {
    const nCopy = new Node(n.val);
    console.log(n.val)
    visited.set(n, nCopy);
    (n.neighbors || []).forEach(ne => {
      if(!visited.has(ne)) {
        dfs(ne);
      }
      nCopy.neighbors.push(visited.get(ne));
    })
  }
  dfs(node)

章节总结

1、图是网络结构的抽象模型，是一组由边连接的节点。
2、图可以表示任何二元关系，比如道路、航道等。
3、JS中没有图，但是可以用Object和Array 构建图。
4、图的表示法:邻接矩阵、邻接表.……。
5、图的常用操作:深度/广度优先遍历。

今天学完了数据结构之“图”，感觉会了，好像也没会，慢慢来吧，日积月累，提升能力，对自己说一句，加油😀~

坚持打卡，坚持学习！明天见💪~

​

​​