js有向图验证是否有回路(环),antv-x6、antv-g6

作者: tww844475003 分类: 前端开发 发布时间: 2021-08-27 00:13
<!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>
前端开发那点事
微信公众号搜索“前端开发那点事”

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注