数据结构-图

图定义

• 图的表示法
  
  

• 图的基本操作
  

图的深度与广度优先遍历

深度优先遍历

// graph.js
// 图 -> 邻接表
const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
};

module.exports = graph;

// dfs.js
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);

广度优先遍历

// graph.js
// 图 -> 邻接表
const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
};

module.exports = graph;

// bfs.js
const graph = require('./graph');

const bfs = (n) => {
  const visited = new Set();  // 5. 声明一个集合存放不重复元素
  visited.add(n);   // 6. 将当前节点添加进去
  const q = [n];    // 1. 定义队列
  while(q.length){
    const n = q.shift();  // 2. 出队并访问
    console.log(n); 
    graph[n].forEach(c => { // 3. 遍历孩子节点
      if(!visited.has(c)){  // 7. 增加判断若是没有访问的相邻节点则继续
        q.push(c);    // 4. 将孩子节点入队
        visited.add(c); // 8. 将孩子节点也添加进集合
      }
    })
  }
}

bfs(2);

刷题

LeetCode: 65. 有效数字

题目描述

解题思路

解题步骤

Code

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    // 1. 构建图
    // blank 表示 ' '   sign 表示 +/-   digit 表示 0~9 .表示点
    const graph = {
        0: { 'blank': 0, 'sign': 1, '.': 2, 'digit': 6 },
        1: { 'digit': 6, '.': 2 },
        2: { 'digit': 3 },
        3: { 'digit': 3, 'e': 4 },
        4: { 'sign': 7, 'digit': 5 },
        5: { 'digit': 5 },
        6: { 'digit': 6, '.': 3, 'e': 4 },
        7: { 'digit': 5 }
    }
    let state = 0; // 初始状态
    // trim() 去除左右两侧的空格
    for (c of s.trim()){    // 2. 将符号进行替换
        if(c >= '0' && c <= '9'){   // 用一个=可以转换格式
            c = 'digit';
        }else if(c === ' '){
            c = 'blank';
        }else if(c === '+' || c === '-'){
            c = 'sign';
        }else if(c === 'e' || c === 'E'){
            c = 'e'
        }
        state = graph[state][c];    // 3. 获取新的状态
        if(state === undefined){    // 若没有此状态，认为无路可走，则返回false
            return false;
        }
    }
    if(state === 3 || state === 5 || state === 6){  // 4. 最后判断 符合条件则认为有效
        return true;
    }
    return false;   // 否则返回false

};

时间复杂度 空间复杂度分析

• 因其中有for循环，所以时间复杂度为O(n)
• 因无线性增长的数组等，只有一个图，内容固定，所以空间复杂度为O(1)

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

题目描述

解题思路

解题步骤

Code

// 不会做 可参考 9-4 LeetCode：417. 太平洋大西洋水流问题.mp4

时间复杂度 空间复杂度分析

• 因其中不断迭代遍历，所以时间复杂度为O(n)
• 因隐含有栈，所以空间复杂度 最差为都分布在一个节点上往下延申为O(n)， 最好为均匀分布为Olog(n)

LeetCode: 133. 克隆图

题目描述

解题思路

解题步骤

Code

// 不会做 可参考 9-5 LeetCode：133. 克隆图.mp4

总结