时间戳

首页 > 解决方案 > 如何在具有相似性的节点之间创建边

javascript - 如何在具有相似性的节点之间创建边

问题描述

我有一个简单的 Graph 类，我必须创建带有节点和边的图。两个节点之间有一条边，nodeA，nodeB如果数组在nodeA和nodeB有一些相似之处。

例如：

const example = [{
  "node": "A",
  "data": [ 1, 2, 3 ]
}, {
  "node": "B",
  "data": [ 3, 4, 5 ]
}, {
  "node": "C",
  "data": [ 5, 6, 7 ]
}, {
  "node": "D",
  "data": [ 7, 8, 9 ]
}]

这意味着：

  1. A并且B因为两个data阵列上都有 3 个。

  2. B并且C因为两个data阵列上都有 5 个。

  3. C并且D因为两个data阵列上都有 7 个。

所以本质上我们有优势A -> B -> C -> D

我设法创建了一个图并使用邻接列表来存储边，但问题是，我不知道如何在具有相似性的节点之间创建边。天真的解决方案是查看example[i - 1]and example[i]。但这是错误的，因为数据不是按顺序排列的。

class Graph {

  constructor(numOfVertex) {

    this.adj = new Map();

  }

  addNodes(node) {

    this.adj.set(node, []);  

  }

  addEdge(nodeA, nodeB) {

    this.adj.get(nodeA).push(nodeB);

    this.adj.get(nodeA).push(nodeB);

  };

}

并填充图表，我这样做：


    const graph = new Graph(example.length);

    for (let i = 0; i < example.length; i++) {

      const { node, data } = example[i];

      graph.addVertex(title)

      G.addEdge(...)

    }

关于如何循环遍历每个节点的数据数组以有效查看相似性的任何想法？

为了这个问题，我给出了一个小的示例数据，实际上，我循环了一大组数据。

标签： javascriptalgorithmgraph

解决方案

根据data数组的大小和结果图的稀疏性，有几种方法可以解决这个问题：

  • 遍历所有节点对并计算它们是否有边。该计算可以O(|data[A]| + |data[B]|)针对一对节点 (A, B) 执行，因此该解决方案的复杂度为O(N^2 + N * (sum of data[i] over all i)). 如果您的图形很密集，即其中的边数约为 N 2 ，则此方法效果很好。
  • 构建一个映射 (X -> ListOfNodes)，这样每个数字 X 都映射到其数据中包含 X 的所有节点。属于同一列表的每一对节点都应该与一条边相连。这个解决方案的复杂性是O((sum of data[i] over all i) + (a hard to estimate quantity that is the number of times each pair of nodes shares a data point))。对于稀疏图，这应该比以前的方法效果更好，但这实际上取决于数据数组的构造方式。

你的数据是如何产生的？

推荐阅读