阅读 452

【译】使用 JavaScript 创建图

banner

图是由具有边的节点集合组成的数据结构。图可以是有向的或者是无向的。

有向图包含功能类似于单行道的边。边缘从一个节点流向另一个节点。

比如,你可能有一个(关于)人物和电影的图表,其中每个人可以有多个喜欢的电影,但是电影没有喜欢的人。

directed_graph

无向图包含双向流动的边缘,类似于双向道路,两个方向都有交通。

比如,你可能有一个宠物图表,其中每只宠物都有一个所有者,每个所有者都有一只宠物。

备注:(下面)双向箭头代表一条边,但是为了显而易见,我绘制了两条箭头。

undirected_graph

**图(graph)**中没有明确的信息层次结构。

方法

我们将创建一个(关于)人和冰淇凌口味的图表。这将是一个有向图,因为人们可以喜欢某些口味,但是味道可不喜欢人。

我们将创建三个类:

  • PersonNode
  • IceCreamFlavorNode
  • Graph

PersonNode

PersonNode类将接受一个参数:一个人的名字。这将作为其标识符。

PersonNode构造函数将包含两个属性:

  • name:唯一标识符
  • favoriteFlavors:关于IceCreamFlavorNodes的数组

另外,PersonNode类包含一个方法:addFlavor。这将传入一个参数,一个IceCreamFlavorNode对象,并将其添加到数组favoriteFlavors中。

类的定义如下所示:

class PersonNode {
  constructor(name) {
    this.name = name;
    this.favoriteFlavors = [];
  }

  addFlavor(flavor) {
    this.favoriteFlavors.push(flavor);
  }
}
复制代码

IceCreamFlavorNode

IceCreamFlavorNode类将传入一个参数:冰淇凌口味。这将作为其标识符。

这个类不需要包含任何方法,因为这是一个无向图,数据是从person流向flavors,但是不会回流。

这个类的定义如下:

class IceCreamFlavorNode {
 constructor(flavor) {
   this.flavor = flavor;
 }
}
复制代码

Graph

Graph类不接受任何参数,但是其构造函数将包含三个属性:

  • peopleNodes:人物节点数组。
  • iceCreamFlavorNodes:冰淇凌口味节点数组。
  • edges:包含PersonNodesIceCreamFlavorNodes之间的边缘数组。

Graph类将包含六个方法:

  • addPersonNode(name):接受一个参数,一个人的名字,创建一个具有此名字的PersonNode对象,并将其推送到peopleNodes数组。
  • addIceCreamFlavorNode(flavor):接受一个参数,一个冰淇凌口味,创建一个具有这种口味的IceCreamFlavorNode对象,并将其推送到iceCreamFlavorNodes数组中。
  • getPerson(name):接受一个参数,一个人名字,并返回该人的节点。
  • getFlavor(flavor):接受一个参数,一个冰淇凌口味,并返回该口味的节点。
  • addEdge(personName, flavorName):接受两个参数,一个人的名称和一个冰淇凌口味,检索两个节点,将flavor添加到人的favoriteFlavors数组,并将边推送到edge数组。
  • print():简单打印出peopleNodes数组中的每个人,以及他们最喜欢的冰淇凌口味。

类的定义如下所示:

class Graph {
  constructor() {
    this.peopleNodes = [];
    this.iceCreamFlavorNodes = [];
    this.edges = [];
  }

  addPersonNode(name) {
    this.peopleNodes.push(new PersonNode(name));
  }

  addIceCreamFlavorNode(flavor) {
    this.iceCreamFlavorNodes.push(new IceCreamFlavorNode(flavor));
  }

  getPerson(name) {
    return this.peopleNodes.find(person => person.name === name);
  }

  getFlavor(flavor) {
    return this.iceCreamFlavorNodes.find(flavor => flavor === flavor);
  }

  addEdge(personName, flavorName) {
    const person = this.getPerson(personName);
    const flavor = this.getFlavor(flavorName);
    person.addFlavor(flavor);
    this.edges.push(`${personName} - ${flavorName}`);
  }

  print() {
    return this.peopleNodes.map(({ name, favoriteFlavors }) => {
      return `${name} => ${favoriteFlavors.map(flavor => `${flavor.flavor},`).join(' ')}`;
    }).join('\n')
  }
}
复制代码

虚拟数据

现在,我们有了三个类,我们可以添加一些数据并测试它们:

const graph = new Graph(true);
graph.addPersonNode('Emma');
graph.addPersonNode('Kai');
graph.addPersonNode('Sarah');
graph.addPersonNode('Maranda');
graph.addIceCreamFlavorNode('Chocolate Chip');
graph.addIceCreamFlavorNode('Strawberry');
graph.addIceCreamFlavorNode('Cookie Dough');
graph.addIceCreamFlavorNode('Vanilla');
graph.addIceCreamFlavorNode('Pistachio');

graph.addEdge('Emma', 'Chocolate Chip');
graph.addEdge('Emma', 'Cookie Dough');
graph.addEdge('Emma', 'Vanilla');
graph.addEdge('Kai', 'Vanilla');
graph.addEdge('Kai', 'Strawberry');
graph.addEdge('Kai', 'Cookie Dough');
graph.addEdge('Kai', 'Chocolate Chip');
graph.addEdge('Kai', 'Pistachio');
graph.addEdge('Maranda', 'Vanilla');
graph.addEdge('Maranda', 'Cookie Dough');
graph.addEdge('Sarah', 'Strawberry');

console.log(graph.print());
复制代码

下面是我们有向图看起来类似(的样子):

demo

如果你想看完整的代码,到我的CodePen上查看。

后话

原文:dev.to/emmawedekin…

文章首发:github.com/reng99/blog…

更多内容:github.com/reng99/blog…

关注下面的标签,发现更多相似文章
评论