数据结构(八)图


图是什么?

  • 图是网络结构的抽象模型,是一组由边连接的节点
  • 图可以表示任何二元关系,比如道路、航班。
  • JS中没有图,但是可以用Object和Array构建图
  • 图的表示法:邻接矩阵,邻接表,关联矩阵

{
  "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);
    }
  });
}

LeetCode #65 有效的数组

LeetCode #417 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

提示:

  • 输出坐标的顺序不重要
  • m 和 n 都小于150
     

示例:

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋
  • 返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解题思路:

  1. 把矩阵想象成图(有向图)
  2. 从海岸线逆流而上遍历图,所到之处就是可以流到某个大洋的坐标
    解题步骤:
  3. 新建两个矩阵,分别记录能流到两个大洋的坐标
  4. 从海岸线,多管齐下,同时深度优先遍历图,过程中填充上边的那个矩阵
  5. 遍历两个矩阵,找出能流到两个大洋的坐标

复杂度:

  1. 时间复杂度O(m * n)
  2. 空间复杂度O(m * n)
/**
 * @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;
};

LeetCode #133 克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

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

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例1:

输入: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 。

示例 2:

  • 输入:adjList = [[]]
  • 输出:[[]]
  • 解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。

示例3:

  • 输入:adjList = []
  • 输出:[]
  • 解释:这个图是空的,它不含任何节点。

示例4:

  • 输入:adjList = [[2],[1]]
  • 输出:[[2],[1]]
     

提示:

节点数不超过 100 。
每个节点值 Node.val 都是唯一的,1 <= Node.val <= 100。
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
图是连通图,你可以从给定节点访问到所有节点。

解题思路:

  1. 拷贝所有节点
  2. 拷贝所有的边

解题步骤:

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

复杂度:

深度优先遍历

  1. 时间复杂度:O(n)
  2. 空间复杂度:O(n)

广度优先遍历

  1. 时间复杂度:O(n)
  2. 空间复杂度:O(n)
/**
 * // 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) // 给定节点的拷贝 作为对克隆图的引用返回。
};

图-章节总结

  • 图是网络结构的抽象模型,是一组由边连接的节点
  • 图可以表示任何二元关系,比如道路,航班.

技术要点

  • JS中没有图,但是可以用Object和Array构件图
  • 图的表示法:邻接矩阵,邻接表...
  • 图的常用操作:深度、广度优先遍历

思考

  1. 用图画出你的朋友圈

声明:Xuhao's Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 数据结构(八)图


Carpe Diem and Do what I like