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

FE情报局

发布于 2022-12-05 10:19:03

4920

发布于 2022-12-05 10:19:03

文章被收录于专栏：FE情报局FE情报局

前端流程图数据结构如何设计？「前端每日一题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

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