数据结构（八）图

1. 定义

图是网络结构的抽象模型，是一组由边连接的节点

图分为有向和无向

图可以表示任何二元关系：比如道路、航班……

js中没有图，使用object和array构建图

图的表示法

• 邻接矩阵：使用二维数组，浪费计算机存储空间，不灵活

  

• 邻接表：使用数组、链表、散列表、字典

​

• 关联矩阵：二维数组；关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存

  

• ……

2. 具体操作

创建

class Graph {
    constructor(isDirected = false) {
        this.isDirected = isDirected;   // 默认情况下为无向
        this.vertices = [];   			// 顶点
        this.adjList = new Dictionary;	// 邻接表
    }
}

方法

• addVertex(v)：添加顶点

  addVertex(v) {
      if (!this.vertices.includes(v)) {
          this.vertices.push(v);
          this.adjList.set(v, []);
      }
  }

• addEdge(v, w)：添加边

  addEdge(v ,w) {
      if (!this.adjList.get(v)) {
          this.addVertex(v);
      }
      if (!this.adjList.get(w)) {
          this.addVertex(w);
      }
      this.adjList.get(v).push(w);
      if (!this.isDirectedn) {
          this.adjList.get(w).push(v);
      }
  }

• getVertices()：返回顶点列表

  getVertices() {
      return this.vertices;
  }

• getAdjList()：返回邻接表

  getAdjList() {
      return this.adjList;
  }

• toString()：返回字符串格式

  toString() {
      let s = '';
      for (let i = 0; i < this.vertices.length; i++) {
          s += `${this.vertices[i]} -> `;
          const neighbors = this.adjList.get(this.vertices[i]); 
          for (let j = 0; j < neighbors.length; j++) {
          	s += `${neighbors[j]} `;
          }
          s += '\n';
      }
      return s;
  }

3. 图的遍历

深度优先遍历：尽可能深的搜索图的分支

• 访问根节点
• 对根节点的没访问过的相邻节点挨个进行深度优先遍历

const graph = {  // 邻接表
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

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 = {  // 邻接表
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

const visited = new Set();
const q = [2];
visited.add(q)
while (q.length) {
    const n = q.shift();
    console.log(n);   // 2 0 3 1
    graph[n].forEach(c => {
        if (!visited.has(c)) {
            q.push(c);
            visited.add(c)
        }
    })
}

4. LeetCode题

65.有效数字

解题步骤：

• 构建一个表示状态的图
• 遍历字符串，并沿着图走，如果到了某个节点无路可走就返回false
• 遍历结束后，直到3、5、6，就返回true

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    const graph = {
        0: { ' ': 0, 'sign': 1, '.': 2, 'num': 6 },
        1: { 'num': 6, '.': 2 },
        2: { 'num': 3 },
        3: { 'num': 3, 'e': 4 },
        4: { 'num': 5, 'sign': 7 },
        5: { 'num': 5 },
        6: { 'num': 6, '.': 3, 'e': 4 },
        7: { 'num': 5 }
    }
    let state = 0;
    for (c of s.trim()) {
        if (c >= '0' && c <= '9') {
            c = 'num'
        } else if (c === ' ') {
            c = ' '
        } else if (c === '+' || c === '-') {
            c = 'sign'
        } else if (c === 'e' || c === 'E') {
            c = 'e'
        }
        state = graph[state][c];
        if (state === undefined) {
            return false;
        }
    }
    if (state == 3 || state === 5 || state === 6) {
        return true;
    }
    return false;
};

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

解题思路：

• 把矩阵想象为图
• 从海岸线逆流而上遍历图，所到之处就是可以流到某个大洋的坐标

解题步骤：

• 新建两个矩阵，分别记录能流到两个大洋的坐标
• 从海岸线，多管齐下，同时深度优先遍历图，过程中填充上述矩阵
• 遍历两个矩阵，找出能流到两个大洋的坐标

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function(heights) {
    if (!heights || !heights[0]) { return [] };
    const m = heights.length;
    const n = heights[0].length;
    const flow1 = Array.from({ length: m }, () => new Array(n).fill(false));
    const flow2 = Array.from({ length: m }, () => new Array(n).fill(false));

    const dfs = (r, c, flow) => {
        flow[r][c] = true;
        [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]].forEach(([nr, nc]) => {
            if(
                // 保证在矩阵中
                nr >= 0 && nr < m &&
                nc >= 0 && nc < n &&
                // 防止死循环
                !flow[nr][nc] &&
                // 保证逆流而上
                heights[nr][nc] >= heights[r][c]
            ) {
                dfs(nr, nc, flow)
            }
        })
    };

    // 沿着海岸线逆流而上
    for (let r = 0; r < m; r++) {
        dfs(r, 0, flow1);
        dfs(r, n - 1, flow2)
    }
    for (let c = 0; c < n; c++) {
        dfs(0, c, flow1);
        dfs(m - 1, c, flow2)
    }

    // 手机能流到两个大洋里的坐标
    const res = [];
    for(let r =0;r<m;r++){
        for(let c = 0;c<n;c++){
            if(flow1[r][c] && flow2[r][c]) {
                res.push([r,c])
            }
        }
    }
    return res
};

133. 克隆图

解题步骤：

• 深度或广度优先遍历所有节点
• 拷贝所有的节点，存储起来
• 将拷贝的节点，按照原图的连接方式进行连接

var cloneGraph = function(node) {
    // 深度优先遍历
    if (!node) return;
    const visited = new Map();
    const dfs = (n) => {
        const nCopy = new Node(n.val);
        visited.set(n, nCopy);
        (n.neighbors || []).forEach(ne => {
            if(!visited.has(ne)) {
                dfs(ne)
            }
            nCopy.neighbors.push(visited.get(ne));
        })
    }
    dfs(node)
    return visited.get(node)
};

var cloneGraph = function(node) {
    // 广度优先遍历
    if (!node) return;
    const visited = new Map();
    visited.set(node, new Node(node.val));
    const q = [node];
    while (q.length) {
        const n = q.shift();
        (n.neighbors || []).forEach(ne => {
            if(!visited.has(ne)) {
                q.push(ne);
                visited.set(ne, new Node(ne.val));
            }
            visited.get(n).neighbors.push(visited.get(ne))
        });
    }
    return visited.get(node)
};