js Graph using Map class - 在哪里存储权重？

Question

我查看了十几个示例，但找不到任何使用 JS Map 对象的加权图（除了没有权重的）。

是否有放置重物的首选位置？

这是基本的 class 结构：

/**
 * @typedef {any} NodeData The Vertex data and used as a key in lists.
 * @typedef {Map<NodeData, Vertex>} AdjacencyList
 */

class Vertex {
  constructor(data) {
    this.data = data;
    /**
     * @type {AdjacencyList}
     */
    this.edges = new Map();
  }
}

class Graph {
  constructor() {
    /**
     * @type {AdjacencyList}
     */
    this.vertices = new Map();
}

我不能把权重放在我的 Vertex class 我想因为同一个顶点可以通过引用成为许多其他顶点的边，所以它需要能够有不同的权重。

我的想法是 Edge class 像这样：

class Edge {
  /**
   * @param {Vertex} point
   * @param {number} weight The cost to travel to this point.
   */
  constructor(point, weight) {
    this.point = point;
    this.weight = weight;
  }
}

但是，这对于在路径中列出节点之类的事情有点烦人，因为混合数据类型 Vertex 和 Edge 因为您首先从 Vertex 开始。为了避免这种情况，它开始变得不那么优雅，我觉得我错过了什么。例如，我可以将第一个 Vertex 访问到具有 0 权重的新 Edge 实例中，这样我就可以得到所有 Edge 类型返回的列表。

此外，对于无向，这意味着相同的权重值被复制到两侧，这让我想知道是否应该避免这种情况。

感谢任何见解！

Answer 1

不要将 edges 映射到它指向的节点的数据。这将使更新节点的数据变得非常麻烦。相反，使用 Map<Vertex, Weight> 作为边缘。

另一种方法是使用两个映射：neighbors: Map<key, Vertex> 和 weights: Map<key, Weight>，您可以在其中确保在您的方法中键集保持同步。但是请注意，普通的 AdjacencyList 只是一个列表，根本没有键控。

js Graph using Map class - 在哪里存储权重？

js Graph using Map class - where to store weight?

javascript

node.js

graph

weighted-graph