<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>js有向图验证是否有回路（环），antv-x6、antv-g6</title>
</head>
<body>
<script>
class isEdgesLoop {
nodesLen = 0
nodes = []
list = {}
queue = []
indegree =[]
constructor(edges) {
edges.forEach(edge => {
const { source, target } = edge
if (!this.nodes.includes(source)) {
this.nodes.push(source)
}
if (!this.nodes.includes(target)) {
this.nodes.push(target)
}
this._addEdge(source, target)
})
this.nodesLen = this.nodes.length
this.nodes.forEach(node => {
if (!this.list[node]) this.list[node] = []
if (!this.indegree[node]) this.indegree[node] = 0
})
}
_addEdge(source, target) {
if (!this.list[source]) this.list[source] = []
if (!this.indegree[target]) this.indegree[target] = 0
this.list[source].push(target)
this.indegree[target] += 1
}
isEdgesLoop() {
Object.keys(this.indegree).forEach(key => {
if (this.indegree[key] === 0) {
this.queue.push(key)
}
})
let count = 0
while (this.queue.length) {
++count
const currentNode = this.queue.pop()
const nodeTargets = this.list[currentNode]
for (let i = 0, len = nodeTargets.length; i < len; i++) {
const target = nodeTargets[i]
this.indegree[target] -= 1
if (this.indegree[target] === 0) {
this.queue.push(target)
}
}
}
// true 没有输出全部顶点，有向图中有回路(环)
return count < this.nodesLen
}
}
const edges = [
{
source: 'node1',
target: 'node2'
},
{
source: 'node2',
target: 'node3'
},
{
source: 'node2',
target: 'node4'
},
{
source: 'node4',
target: 'node5'
},
{
source: 'node5',
target: 'node2'
}
];
const isLoop = new isEdgesLoop(edges)
console.log(isLoop.isEdgesLoop())
</script>
</body>
</html>
微信公众号搜索“前端开发那点事”
