{
  "V1"：["V2", "V3", "V4"],
  "V2": [],
  "V3": ["V4"],
  "V4": ["V1"]
}

// graph.js
const graph ={
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
}
module.exports = graph;

// 图的深度优先遍历实现
const graph= require('./graph');
// 用来记录已访问过的节点
const visited = new Set();
const dfs = (n)=>{
  console.log(n);
  visited.add(n);
  graph[n].forEach(c => { // 拿到所有相邻节点
    if(!visited.has(c)){ // 还未访问过的相邻接点
      dfs(c);
    }
  });
};
dfs(2);

// 图的广度优先遍历实现
const graph = require('./graph')
const visited = new Set();
visited.add(2);
const queue = [2];
while(queue.length){
  const n = queue.shift();
  console.log(n);
  graph[n].forEach(c => {
    if(!visited.has(c)){
      queue.push(c);
      visited.add(c);
    }
  });
}

  太平洋 ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * 大西洋

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
    if(!matrix || !matrix[0]){
        return [];
    }
    const m = matrix.length;
    const n = matrix[0].length;
    // 构建数组的两种方法1. Array.from({length:n}) 2. new Array(n)
    const flow1 = Array.from({length: m}, ()=> {return new Array(n).fill(false)});  // 能流到太平洋的矩阵
    const flow2 = Array.from({length: m}, ()=> {return new Array(n).fill(false)}); // 能流到大西洋的矩阵
    const dfs = (row, cow, flow)=>{ // 行，列
        flow[row][cow] = true;
        [[row-1, cow], [row+1, cow], [row, cow-1], [row, cow+1]].forEach(([nextrow, nextcow])=>{ 
          // 相邻的上，下，左，右四个节点的数组遍历
            if(
                //保证下一个节点在矩阵中
                nextrow >= 0 && nextrow < m  &&
                nextcow >= 0 && nextcow < n  &&
                // 防止死循环，即保证未访问过该节点
                !flow[nextrow][nextcow] && 
                // 保证逆流而上
                matrix[nextrow][nextcow] >= matrix[row][cow]
            ){ 
                dfs(nextrow, nextcow, flow)
            }
        })
    };
    // 沿着海岸线逆流而上
    for(let row=0; row<m; row++){
        dfs(row, 0 ,flow1); // 从第一行到最后一行，保证第一列，流到太平洋
        dfs(row, n-1, flow2); // 遍历最后一列的格子，流到大西洋 传flow2
    }
    for(let cow=0; cow<n; cow++){
        dfs(0, cow, flow1); // 遍历第一行，太平洋
        dfs(m-1, cow, flow2); // 遍历最后一行，大西洋
    }
    // 收集能流到两个大洋的坐标
    const res = [];
    for(let row=0; row<m; row++){ // 遍历所有行
        for(let cow=0; cow<n; cow++){ // 遍历所有列
            if(
                flow1[row][cow] && // 能流到太平洋
                flow2[row][cow] // 能流到大西洋
            ){
                res.push([row,cow])
            }
        }
    }
    
    // console.log(flow1)
    // console.log(flow2)
    return res;
};

class Node {
    public int val;
    public List<Node> neighbors;
}

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if(!node){
        return;
    }
    const visited = new Map(); // 记录映射关系
    // 深度优先遍历实现
    const dfs = (node) => {
        // console.log(node.val) // 访问节点
        // 拷贝每一个节点
        const nCopy = new Node(node.val); 
         // 节点存放到已访问, 建立映射关系
        visited.set(node, nCopy);
        (node.neighbors || []).forEach(nodeneighbors=>{
            // 如果没有neighbors 转换成[]
            if(!visited.has(nodeneighbors)){
                dfs(nodeneighbors);
            }
            // 拷贝所有的边
            nCopy.neighbors.push(visited.get(nodeneighbors));
        })
    };
    dfs(node);
    // 给定节点的拷贝 作为对克隆图的引用返回。
    return visited.get(node) 
};

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if(!node){
        return;
    }
    const visited = new Map(); // 记录映射关系
    visited.set(node, new Node(node.val))
    // 广度优先遍历实现
    const queue = [node];
    while(queue.length){
        const n = queue.shift(); // 拿出对头并访问
        // console.log(n.val);
        (n.neighbors || []).forEach(nodeneighbors=>{ 
          // 访问所有邻居节点
            if(!visited.has(nodeneighbors)){
                queue.push(nodeneighbors);
                // 拷贝节点
                visited.set(nodeneighbors, new Node(nodeneighbors.val));
            }
            // 拷贝边
            visited.get(n).neighbors.push(visited.get(nodeneighbors));
        })
    }
    return visited.get(node) // 给定节点的拷贝 作为对克隆图的引用返回。
};