My Muri Life

切换主题

本页目录

有向图 ​

本篇来手动实现JavaScript中没有的数据结构：有向图。

定义节点 ​

首先定义有向图节点结构：

JavaScript
class Node {
  constructor(val) {
    this.val = val
    this.in = 0  // 入度
    this.out = 0  // 出度
    this.nexts = []  // 由当前节点出发，直接到达的节点（直接邻居）
    this.edges = []  // 与直接邻居形成的边
  }
}
class Edge {
  constructor(weight, fNode, tNode) {
    this.weight = weight
    this.from = fNode  // 出发节点
    this.to = tNode  // 到达节点
  }
}
class Graph {
  constructor() {
    this.nodes = new Map()  // { fNode.val/tNode.val : Node }
    this.edges = new Set()
  }
}

实现有向图 ​

假设现有一矩阵matrix，矩阵每项有[weight, fNode.val, tNode.val]，在此基础上实现有向图。

JavaScript
class Digraph {
  constructor(matrix) {
    this.digraph = new Graph()
    // 初始化
    for (const ele of matrix) {
      const [weight, fVal, tVal] = ele  // 解构
      if (!this.digraph.nodes.has(fVal)) {
        this.digraph.nodes.set(fVal, new Node(fVal))
      }
      if (!this.digraph.nodes.has(tVal)) {
        this.digraph.nodes.set(tVal, new Node(tVal))
      }
      // 获取节点与创建对应的边
      const fNode = this.digraph.get(fVal)
      const tNode = this.digraph.get(tVal)
      const edge = new Edge(weight, fNode, tNode)
      // 构建有向图
      fNode.nexts.push(tNode)  // 添加直接邻居
      fNode.out++  // 更新出度
      tNode.in++  // 更新出度
      fNode.edges.push(edge)  // 更新边
      this.digraph.edges.add(edge)  // 更新边集
    }
  }
}

拓扑排序 ​

该排序算法使用范围为无环且有入度为0的节点的有向图，同时也会用到hashMap与队列两个数据结构：

  • hashMap：用于存放节点与节点的入度值，即{ node : node.in }；
  • 队列：用于存放入度为0的节点。

算法过程描述：

  1. 首先遍历无环有向图：
    1. 根据图节点初始化map数据；
    2. 找出第一个入度为0的节点，将其入队。
  2. 当队列不为空时，出队入度为0的节点，记为curr：
    1. 记录当前出队节点curr；
    2. 遍历直接邻居，削弱出队节点curr的影响（这里的影响是指：从curr出发，到达的直接邻居所构成的边，即curr为直接邻居贡献的入度）；
    3. 在2.2遍历中找出下一个入度为0的节点并入队。
  3. 当队列为空时，拓扑排序完成。
JavaScript
const topoSort = (digraph, ret = []) => {
  const [map, queue] = [new Map(), []] // { node : node.in }
  // 获取nodes
  const nodes = digraph.nodes.values()
  for (const node of nodes) {
    map.set(node, node.in)
    // 第一个入度为 0 的节点
    if (node.in === 0) queue.push(node)
  }
  // 排序
  while (queue.length) {
    const curr = queue.shift()
    ret.push(curr)
    for (const next of curr.nexts) {
      // 削弱其影响，即直接邻居的入度
      map.set(next, map.get(next) - 1)
      // 下一个入度为 0 的节点
      if (map.get(next) === 0) queue.push(next)
    }
  }
}

数据结构应用 ​

leetcode
  1. 拓扑排序