由DAG图的环路检测学习Set和Map

发表于

业务上有一个需求是检测工作流模板是否是DAG图，DAG图即有向无环图，常见的解决方法是拓扑排序，如果存在环路，则不能进行拓扑排序。

拓扑排序

拓扑排序是有向无环图所有顶点的线性序列。

满足两个条件：

  1. 每个顶点只出现一次
  2. 若存在从A到B的路径，那么序列中A出现在B之前

环路检测算法

  1. 找到入度为0的点，输出该点
  2. 删除该点及该点的所有出边
  3. 重复步骤一二，直到输出图中所有节点，如果图中有节点未输出，则存在环路

实现

例如下图存在环路

1. 确定数据格式

1
2
3
4
5
6
7
8
9
const edges = [
	{ source: 'start', target: '1' },
	{ source: '1', target: '2' },
	{ source: '2', target: '3' },
	{ source: '3', target: '2' },
	{ source: 'start', target: '4' },
	{ source: '4', target: '3' }
];
const nodes = ['start', '1', '2', '3', '4'];

2.创建邻接表存储图的信息

1
2
3
4
5
6
7
8
9
10
11
12
const nodeSet = new Set(nodes);
const graph = new Map();
for (let i = 0; i < edges.length; i++) {
	const { source, target } = edges[i];
	// 将该边加入到邻接表中
	if (!graph.has(source)) {
	  graph.set(source, []);
	}
	const sourceArr = graph.get(source);
	sourceArr.push(target);
	graph.set(source, sourceArr);
}
1
2
3
4
5
6
7
8
9
10
// graph 数据
Map {
  'start' => [ '1', '4' ],
  '1' => [ '2' ],
  '2' => [ '3' ],
  '3' => [ '2' ],
  '4' => [ '3' ]
}
// node 数据
Set { 'start', '1', '2', '3', '4' }

3.找到入度为0的点，删除所有出边

1
2
3
4
5
// 'start'为第一个入度为0的节点
graph.delete('start');
nodeSet.delete('start');
// 删掉的节点缓存起来
stack.push('start');

删除start之后的 graph 与 node

1
2
3
4
5
Map { '1' => [ '2' ], 
'2' => [ '3' ], 
'3' => [ '2' ], 
'4' => [ '3' ] }
Set { '1', '2', '3', '4' }

graph中，key代表线的出点，value代表线的入点，将value去重后，与nodeSet 取差集就得到下一批入度为0的节点。

1
2
3
4
5
6
7
8
9
10
nodeSet.forEach(() => {
    const diff = getZeroNode(graph, nodeSet);
    if (diff.length) {
      diff.forEach((item) => {
        stack.push(item);
        graph.delete(item);
        nodeSet.delete(item);
      });
    }
  });
1
2
3
4
5
6
7
8
// 找到入度为0的节点
function getZeroNode(graph, nodeSet) {
  // graph 取 value 去重 
  const graphArr = new Set([...graph.values()].flat());
  //  与node Set 取差集
  const diff = new Set([...nodeSet].filter((x) => !graphArr.has(x)));
  return [...diff];
}

4.判断栈内节点数，若小于原始节点数则存在环路

1
2
3
4
if (stack.length < nodes.length) {
    return true;
  }
  return false;

实践中用到的Set和Map实例方法

Set

类似数组，但是成员的值唯一。

  • delete(value) 删除某个值，返回布尔值，表示是否删除成功
  • has(value) 返回布尔值，表示参数是否为成员

数组去重

[...new Set(array)]

并集

new Set([...a, ...b])

交集

new Set([...a].filter(x => b.has(x)))

差集

new Set([...a].filter(x => !b.has(x)))

Map

类似对象，也是键值对的集合。但是"键"不限于字符串，各种类型都可以做为键。

  • set(key, value) 设置key对应的键值
  • get(key) 读取key对应的键值
  • has(key) 返回布尔值，表示某个键是否再Map数据结构中
  • delete(key) 删除某个键

Map的遍历方法

  • values() 返回键值的遍历器