数据结构 — 图

图（graph）是一种数据结构，由一组节点或顶点以及一组表示这些节点之间连接的边组成。图可以是有向的或无向的，而它们的边可以分配数字权重。

JavaScript 图可视化

图数据结构中的每个节点都必须具有以下属性：

• key：节点的键
• value：节点的值

图数据结构中的每条边都必须具有以下属性：

• a：边的起始节点
• b：边的目标节点
• weight：边缘的可选数字权重值

图数据结构的主要操作有：

• addNode：插入具有特定键和值的新节点
• addEdge：在两个给定节点之间插入一条新边，可选择设置其权重
• removeNode：删除具有指定键的节点
• removeEdge：删除两个给定节点之间的边
• findNode：检索具有给定键的节点
• hasEdge：检查图在两个给定节点之间是否有边
• setEdgeWeight：设置给定边的权重
• getEdgeWeight：获取给定边的权重
• adjacent：从给定节点查找存在边的所有节点
• indegree：计算给定节点的总边数
• outdegree：计算给定节点的总边数

JavaScript 实现

class Graph {
  constructor(directed = true) {
    this.directed = directed
    this.nodes = []
    this.edges = new Map()
  }

  addNode(key, value = key) {
    this.nodes.push({ key, value })
  }

  addEdge(a, b, weight) {
    this.edges.set(JSON.stringify([a, b]), { a, b, weight })
    if (!this.directed) this.edges.set(JSON.stringify([b, a]), { a: b, b: a, weight })
  }

  removeNode(key) {
    this.nodes = this.nodes.filter(n => n.key !== key)
    ;[...this.edges.values()].forEach(({ a, b }) => {
      if (a === key || b === key) this.edges.delete(JSON.stringify([a, b]))
    })
  }

  removeEdge(a, b) {
    this.edges.delete(JSON.stringify([a, b]))
    if (!this.directed) this.edges.delete(JSON.stringify([b, a]))
  }

  findNode(key) {
    return this.nodes.find(x => x.key === key)
  }

  hasEdge(a, b) {
    return this.edges.has(JSON.stringify([a, b]))
  }

  setEdgeWeight(a, b, weight) {
    this.edges.set(JSON.stringify([a, b]), { a, b, weight })
    if (!this.directed) this.edges.set(JSON.stringify([b, a]), { a: b, b: a, weight })
  }

  getEdgeWeight(a, b) {
    return this.edges.get(JSON.stringify([a, b])).weight
  }

  adjacent(key) {
    return [...this.edges.values()].reduce((acc, { a, b }) => {
      if (a === key) acc.push(b)
      return acc
    }, [])
  }

  indegree(key) {
    return [...this.edges.values()].reduce((acc, { a, b }) => {
      if (b === key) acc++
      return acc
    }, 0)
  }

  outdegree(key) {
    return [...this.edges.values()].reduce((acc, { a, b }) => {
      if (a === key) acc++
      return acc
    }, 0)
  }
}

• 创建一个具有 constructor 的类（class），为每个实例初始化空数组、nodes、Map 和 edges。可选参数 directed 指定图形是否有方向。
• 定义一个 addNode() 方法，使用 Array.prototype.push() 在 nodes 数组中添加新节点。
• 定义一个 addEdge() 方法，使用 Map.prototype.set() 向 edgesMap 添加新边，JSON.stringify() 用于生成唯一键。
• 定义一个 removeNode() 方法，使用 Array.prototype.filter() 和 Map.prototype.delete() 删除给定的节点及其连接的所有边。
• 定义一个 removeEdge() 方法，使用 Map.prototype.delete() 删除给定的边。
• 定义一个 findNode() 方法，使用 Array.prototype.find() 返回给定节点（如果有）。
• 定义一个 hasEdge() 方法，使用 Map.prototype.has() 和 JSON.stringify() 检查给定的边是否存在于 edges Map 中。
• 定义一个 setEdgeWeight() 方法，使用 Map.prototype.set() 设置相应边的权重，该边的键由 JSON.stringify() 生成。
• 定义一个 getEdgeWeight() 方法，使用 Map.prototype.get() 获取相应边的 8 个，该边的键由 JSON.stringify() 生成。
• 定义一个 adjacent() 方法，使用 Map.prototype.values()、Array.prototype.reduce() 和 Array.prototype.push() 查找连接到给定节点的所有节点。
• 定义一个 indegree() 方法，使用 Map.prototype.values() 和 Array.prototype.reduce() 计算给定节点的边数。
• 定义一个 outdegree() 方法，使用 Map.prototype.values() 和 Array.prototype.reduce() 计算给定节点的边数。

const g = new Graph()

g.addNode('a')
g.addNode('b')
g.addNode('c')
g.addNode('d')

g.addEdge('a', 'c')
g.addEdge('b', 'c')
g.addEdge('c', 'b')
g.addEdge('d', 'a')

g.nodes.map(x => x.value) // ['a', 'b', 'c', 'd']
;[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`)
// ['a => c', 'b => c', 'c => b', 'd => a']

g.adjacent('c') // ['b']

g.indegree('c') // 2
g.outdegree('c') // 1

g.hasEdge('d', 'a') // true
g.hasEdge('a', 'd') // false

g.removeEdge('c', 'b')
;[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`)
// ['a => c', 'b => c', 'd => a']

g.removeNode('c')

g.nodes.map(x => x.value) // ['a', 'b', 'd']
;[...g.edges.values()].map(({ a, b }) => `${a} => ${b}`)
// ['d => a']

g.setEdgeWeight('d', 'a', 5)
g.getEdgeWeight('d', 'a') // 5

以上内容译自 30 seconds of code 的 JavaScript Data Structures - Graph

更多资料

Graph (both directed and undirected)