【算法】如何确定图（Graph）里有没有环（Cycle）？

“判断图中是否有环”是一道经常出现在面试中经典的算法题，我们今天就来讲讲这道题的含义和解法，包含Python编码全过程。

题目中的概念

判断图中是否有环这道题目首先涉及到两个概念：图和环。

这里的图就是计算机数据结构中说的图结构（Graph），它包括两个要素：顶点和边，前者又称为节点。

节点表示事物的抽象，而边则表示事物之间两两的联系。

边可以分为有方向和无方向两种。有方向的边表示两个节点之间单向的连通，而无方向的边则表示双向连通。边有方向的图叫做有向图，反之叫做无向图。

环则是指在途中一条由边组成的路径，从一个节点出发，可以回到这个节点自身。

判断无向图中是否有环

通过上面的定义可知，无论有向图还是无向图中都存在环，但有向图的环涉及到边的方向，要比无向图复杂。

因此，如果你在面试中被要求写一个算法“判断图中是否有环”，首先就应该和面试官确认，要判断的是有向图还是无向图。本文我们讲解的是无向图中是否有环的判断！

比如下面这两个无向图，很显然图一里面有环，而图二没有。

从算法的原理开始

用眼睛看起来很简单的事情，如何用程序来实现呢？

在动手编程之前，我们首先要想清楚如何做，也就是说我们先要能够找到一个用自然语言可以描述的办法，来确定无向图中是否有环。

其实很多算法最难的一点实在这里，平白的给你一张无向图，你能找出一个切实可行的办法，把它描述出来，别人只要按照指示去做，就一定能正确地确认任何一个无向图里面有没有环吗？

如果你从来没有学过相关的知识，自己拍脑袋就想出这样的一个办法来了！那么恭喜，你已经具备了创造算法的能力！不过对于大多数人来说，我们还是需要寻求前人的帮助。

最简单的方法：在互联网上查找一下。我们在搜索引擎中输入“判断无向图有没有环”这个查询语句，然后看到很多相关的搜索结果。

我们直接点击第一个。看到了下面这个文章。

本文中讲的内容比较多，介绍了三种方法：拓扑排序，DFS和Union-Find Set，每一种方法都可以判断无向图或者有向图。

拓扑排序法判断一个无向图中是否有环

“判断一个无向图有没有环”的方法本文中就有三个。这里，我们先取第一种方法：拓扑排序判断无向图是否有环。这种方法的描述如下：

使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：

    1. 求出图中所有节点的度。

    2. 将所有度 <= 1 的节点入队。

    3. 当队列不空时进入循环，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为1，则将相邻节点入队。队列为空则退出循环。

    4. 循环结束时判断已经访问过（进入过队列）的节点数是否等于 n。等于 n 说明全部节点都被访问过，无环；反之，则有环。

我们将算法改写成控制流程图是下面这样：

这里面又涉及到了一个概念——节点的度。

什么叫做节点的度呢？其实很简单，节点的度是指和该节点相关联的边的条数。

如果是有向图，还要分入度和出度，不过我们现在要处理的是无向图，所以，每条边都是平等的，统一都记作度数。

人肉模拟运行算法

我们来找两个例子，按照算法模拟运行一下。

第一个例子

先看图一，图一中节点1，2，3的度是2，节点4和5的度是3，而节点6和7的度是1。

那首先，我们要把节点6和7放到队列里。

然后将节点6弹出，把和节点6相邻的节点5的度减一。从图上，就相当于擦掉了节点5和节点6之间的边。按理说此时节点6的度也应该减掉1，但是因为节点6我们已经处理过，它以后不会再进入队列，我们也不不会再关心它的度，因此也不用去处理它的度了。

此时队列还没有空，所以我们继续弹出队首并处理。弹出节点7，将和它相邻的节点4的度减一，相当于删除了它们之间的边。

现在队列已经弹空，退出了循环。我们再看进入过队列的节点只有2个，而节点一共有7个，2 不等于 7， 所以有环。

第二个例子

现在再来看图二，一共5个节点，相应的度分别是1，2，2，2，1。

此第一拨入队列的是度为1的节点1和节点5。

节点1出队列后和它相邻的节点2度数减一，也变成了度为1的节点，因此节点2入队列。

再度进入循环，弹出节点5，和它相邻的节点4度数减一后入队列。继续循环弹出节点2，节点3入队列。

循环弹出节点4，节点3的度变成0，不用再度入栈。

最后一次循环弹出节点3，和它相邻的再无度为1的节点，循环结束。

至此，所有节点都已经入过队列，因此可知，无环。

直观来看，算法是有效的。

确定数据结构

那么下面是不是就该编程实现了？稍等，别忘了，程序 = 算法 + 数据结构。我们现在只有算法，还没有描述无向图的数据结构。

图的表示方法不止一种，此处我们采用邻接矩阵表示无向图。很多时候，当面试官出题要求判断图中是否有环时，会特意指出要用邻接矩阵。如果没指出，就是让你自选。

邻接矩阵是一个 n 阶的方阵，n 为图中顶点个数。方阵中每个元素的值只有两种可能，要么 0 ，要么 1。若第 i 行第 j 列的元素为 1，则说明 i 节点和 j 节点相邻，也就是有一条无向边存在于二者之间，若为 0，则说明节点 i 和 j 不相邻。

由此图一和图二对应的矩阵分别是这样：

邻接矩阵也可以用在有向图上。

不过对无向图而言：

    i) 邻接矩阵一定是对称的，而且主对角线一定为零（自己不可能和自己相邻）。

    ii) 在无向图中，节点 i 的度是矩阵第 i 行（或第 i 列）所有非零元素的个数。因为非零元素的取值只能是 1，因此节点 i 的度也是邻接矩阵第 i 行所有值的和。

另一方面，方阵就是一个二维表，在程序内部，正好用一个二位数组或列表（List）来表示。

很好，既然如此，我们就可以开始编程了。

编程实现算法

我们用Python来编。

在正式实现算法之前，我们先要进行数据处理，也就是我们需要将表达无向图的矩阵读取到内存中。

这里又涉及到该数据在磁盘存储的问题。我们就用最简单的方式，将邻接矩阵直接存储为 csv 文件，就像这样：

我们专门定义一个函数（如下图）做数据处理，那么在读取的时候，我们就可以用 Python的csv library，用csv.reader() 读取 csv文件，然后再转化为列表。这个列表就是算法的输入。

现在来看算法本身。

我们定义一个函数，名为 is_undirected_graph_circled，它接受一个输入参数：adj_matrix，这个adj_matrix 是一个二维表。

要处理二维表，也就是输入的邻接方阵，我们首先要知道方阵的阶数，那么很好办，我们只要用 len 函数，就可以。

然后我们要计算所有节点的度，并且将度  <=1 的节点压入队列。这里要用到队列，我们就用Python自带的queue library，先import，然后直接创建一个队列。

接着计算每个节点的度，将它们存储在degrees列表里，用一个循环，每个循环对用矩阵的一行，然后 sum函数将该行中所有的元素相加。

这里有一点要注意，我们直接用csv.reader读取出来的数据是字符串，我们要对其进行数据转换，将其转化为整数型，这样才能有效地计算度。

算出一个节点的度后直接判断是否小于等于 1，若是则入队列。

这里还要注意一件事情，我们的算法最终要判断有多少节点入过队，但是队列本身要不断地压入弹出，里面不可能保留所有入过队的节点。所以要用一个专门的列表存储每个入队的元素。就是这个visited。

做完这些就该进入到最核心的循环部分了。循环中的关键则是：把与队首元素相邻节点的度减 1。

我们该怎么找到与队首节点相邻的节点呢？比如节点 i，在邻接方阵里，第 i 行和第 i 列的所有元素都记录了它的邻居，那么我们可以选取第 i 行作为线索，找到所有值为 1 的元素，该元素所在的列数 j 所对应的 j 节点，就是与 i 相邻的节点。

那么我们需要将degrees里对应 j 元素的值减去 1。然后看看它减掉 1 后的值是否为 1，若是则入队，否则不管。

当队中元素全部弹出后，循环结束，我们看看 visited 列表中的元素个数是否已经达到了 n 个，若是则说明无环，否则有环。

算法函数定义好之后，可以在数据处理函数中调用，然后把结果打印出来。

完整代码和数据请见： 

https://github.com/juliali/ClassicAlgorithms/tree/main/undirected_graph

尽职尽才，允公允能 —— 本社群不定期举行线上分享，组织群友分享知识、经验、资源，以达到让我们每个人的职业生涯得到最大程度的发展的目的。

欢迎扫面下列二维码关注“悦思悦读”公众微信号