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

题目中的概念

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

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

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

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

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

判断无向图中是否有环

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

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

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

从算法的原理开始

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

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

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

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

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

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

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

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

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

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

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