JavaScript数据结构 - 图

定义

图是由一组节点或顶点和表示这些节点之间连接的一组边组成的数据结构。图可以是有向的或无向的，而它们的边可以被赋予数值权重。

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

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

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

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

图数据结构的主要操作包括：

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

实现

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

• 创建一个class，其中的constructor初始化一个空数组nodes和一个Map edges，用于每个实例。可选参数directed指定图是否是有向的。

• 定义一个addNode()方法，使用Array.prototype.push()将一个新节点添加到nodes数组中。

• 定义一个addEdge()方法，使用Map.prototype.set()将一个新边添加到edges Map中，使用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()来获取适当边的权重，其键由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