检测无向图有没有闭环

这篇文章来自工作中的一个实际问题：电子工程师在进行电路设计时，一般不用画出有闭环的导线，否则就短路了，这个是没有意义的。为了避免电子工程师的误操作，需要做这么一个防呆的工作。这是一个实际的场景，为了解决这个问题，可以转换成一个图的问题。

先来解释几个概念。

什么是图？

图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

维基百科

用我自己的理解，再加上一些土话来说就是：将一些问题抽象成点、边，研究他们的关系。

什么是元件？

在图论中，元件又称为连通元件、分量、或分支，是一个无向子图，在元件中的任何两个顶点都可以经由该图上的边抵达另一个顶点，且没有任何一边可以连到其他子图的顶点。

维基百科

元件也可以称为联通分量，就是单独的一块图，和其它的图不相连。

先看实际效果

点击刷新，重看效果

下图有 10 个节点，随机生成了一些边。

图的表示方法

图的表示方法常见的有 2 种，一种是邻接表，一种是邻接矩阵，两者都可以用数组来表达。邻接表一般用来表示稀疏图，邻接矩阵用来表示稠密图。

在这个例子里，如下代码生成邻接表：

generateAdjacencyList() {
  for (let i = 0; i < this.dots; i++)
  for (let j = i + 1; j < this.dots; j++) {
    if (Math.random() > 0.9) {
    // 无向图 i，j 是互相对应的
    this.adjacencyList[i].push(j);
    this.adjacencyList[j].push(i);
    }
  }
}

针对某个稀疏图，这篇文章主要回答如下几个问题：

• 这个图里有几个联通分量？
• 有没有闭环？有几个闭环？
• 如何实现此图的深度优先遍历？

深度优先遍历

dfs() {
  // parent 参数用来检测有没有闭环
  let dfs = (i, parent) => {
    // 记录哪些节点已经访问过，不 true、false 表示，用联通分量的数量，
    // 可以方便记录哪些边在同一个联通分量
    this.visited[i] = this.count;

    for (const index of this.adjacencyList[i]) {
      if (!this.visited[index]) {
        dfs(index, i);
      } else if (parent !== index) {
        this.map.set(this.count, true);
      }
    }
  };

  for (let i = 0; i < this.allCircle.length; i++) {
    if (!this.visited[i] && this.adjacencyList[i].length) {
      // 统计联通分量数量
      this.count++;
      // 深度优先遍历
      dfs(i, -1);
    }
  }

  console.log(this.visited, this.count, this.map);
}

参考链接

• Detect cycle in an undirected graph
• 深度优先遍历和联通分量