feer.cc

V1

2022/11/13阅读:16主题:全栈蓝

前端流程图数据结构如何设计?「前端每日一题v22.11.10」

前端流程图数据结构如何设计?「前端每日一题v22.11.10」

定义

什么是Graph?翻译过来就是图形,图标。比如我们常见的流程图,xmind都可以称为Graph,它是一种数据结构,可以通过点和矢量线来表示其中的节点关系,类似这种

分析

可以尝试分析一下这张图,A、B、C、D分别为节点,连接对应关系的我们暂且称之为连接线,或者边

每一个节点在数据结构中必须存在以下两个属性

  • key:这个节点的key,可以将其看为唯一的ID
  • value:节点中对应的数据

每一个连接线或者边在数据结构中也必须存在以下属性

  • start:边开始的节点
  • end:边结束的节点
  • weight:边的权重

有了以上信息,我们就可以开始我们的代码

逻辑

首先,我们需要定义一个Graph的类,这个类包含节点数组合集,边的Map,还有一个参数表示连接节点的边是否是一个带有方向的边

这里为什么用Map,是因为Map的特性,可以使用复杂数据类型当作其对应的key

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

有了初始化的内容,第一步要做的事就是在画布中添加节点,添加节点需要定义一个方法,将节点添加到nodes数组中,这里我们默认代码在Graph的类中

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

同样的,我们也需要一个添加边的方法,这里要注意,我们在初始的时候定义了一个边是否有方向,如果没有方向的话那就需要双向连接,有方向表示一个单项连接

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

有添加就有删除,那如何删除对应的node节点?首要的是我们需要找到对应的node节点,那唯一的节点id就是其对应的key。可以将要删除的节点从整个节点list中移除

删除了节点之后还需要删除其对应的线,条件就是这条线开始节点和结束节点都在要删除的节点上

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

移除连接线

removeEdge(start, end) {
  this.edges.delete(JSON.stringify([start, end]));
    if (!this.directed) this.edges.delete(JSON.stringify([end, start]));
}

剩下的就是一些比较简单的查找类的方式方法

// 查找对应的node
findNode(key) {
  return this.nodes.find(x => x.key === key);
}
// 是否存在某一条线
hasEdge(start, end) {
  return this.edges.has(JSON.stringify([start, end]));
}

setEdgeWeight(start, end, weight) {
  this.edges.set(JSON.stringify([start, end]), { start, end, weight });
  if (!this.directed)
    this.edges.set(JSON.stringify([end, start]), { start: end, end: start, weight });
}

getEdgeWeight(start, end) {
  return this.edges.get(JSON.stringify([start, end])).weight;
}

// 获取某个节点相连的对应的节点
adjacent(key) {
  return [...this.edges.values()].reduce((acc, { start, end }) => {
    if (start === key) acc.push(end);
    return acc;
  }, []);
}

// 有多少个节点在某个节点结束
indegree(key) {
  return [...this.edges.values()].reduce((acc, { start, end }) => {
    if (end === key) acc++;
    return acc;
  }, 0);
}

// 某个节点连接跟多少节点有连接
outdegree(key) {
  return [...this.edges.values()].reduce((acc, { start, end }) => {
    if (start === key) acc++;
    return acc;
  }, 0);
}

将上述的代码逻辑封装整理,最终的Graph实例如下

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

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

  addEdge(start, end, weight) {
    this.edges.set(JSON.stringify([start, end]), { start, end, weight });
    if (!this.directed)
      this.edges.set(JSON.stringify([end, start]), { start: end, end: start, weight });
  }

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

  removeEdge(start, end) {
    this.edges.delete(JSON.stringify([start, end]));
    if (!this.directed) this.edges.delete(JSON.stringify([end, start]));
  }

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

  hasEdge(start, end) {
    return this.edges.has(JSON.stringify([start, end]));
  }

  setEdgeWeight(start, end, weight) {
    this.edges.set(JSON.stringify([start, end]), { start, end, weight });
    if (!this.directed)
      this.edges.set(JSON.stringify([end, start]), { start: end, end: start, weight });
  }

  getEdgeWeight(start, end) {
    return this.edges.get(JSON.stringify([start, end])).weight;
  }

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

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

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

具体的使用进行验证

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

这种数据结构就满足我们刚开始说的这种连接关系

JavaScript Data Structures - Graph[1]

Reference

[1]

参考文章: https://www.30secondsofcode.org/articles/s/js-data-structures-graph。

分类:

前端

标签:

前端

作者介绍

feer.cc
V1

微信公众号:FE情报局