专栏首页悦思悦读【算法】如何确定图(Graph)里有没有环(Cycle)?

【算法】如何确定图(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

本文分享自微信公众号 - 悦思悦读(yuesiyuedu),作者:YJL

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Swift Reference Cycle中的weak,unowned,Closure Capture List

    如果您在用Swift做iOS开发,且暂时不是很清楚什么时候用weak、什么时候用unowned、或者不是很清楚什么是closure capture list,那...

    iOS Development
  • Python 弱引用的使用

    和许多其它的高级语言一样,Python使用了垃圾回收器来自动销毁那些不再使用的对象。每个对象都有一个引用计数,当这个引用计数为0时Python能够安全地销毁这个...

    用户2936342
  • 数据结构(九):广度优先与深度优先

    广度优先搜索(breadth-first search)和深度优先搜索(depth-first search)是两种探索图/树中顶点的思路。这两种搜索方式可以用...

    zhipingChen
  • ​2021-03-12:go中,如何确定有没有内存泄露,系统里怎么去监控整体?

    2021-03-12:go中,如何确定有没有内存泄露,系统里怎么去监控整体的运行情况,日志是怎么处理的?

    福大大架构师每日一题
  • 不求甚解之 Spanning Tree

    最近在阅读 USB4 的标准,文档中多次提到 Spanning Tree,于是网上搜了搜,大概有了些概念,写下来促进理解。

    icsoc
  • 使用连续局部聚合对图信号进行采样(CS)

    提出了一种对图节点中定义的信号进行采样的新方案。基本假设是此类信号在与图结构相关的频域中允许稀疏表示,这由所谓的图移位算子捕获。大多数研究这个问题的工作都集中在...

    用户8380959
  • 修正重发【CPLEX教程03】JAVA调用cplex求解一个TSP模型详解

    前面我们已经搭建好cplex的java环境了,详情可以看干货 | cplex介绍、下载和安装以及java环境配置和API简单说明,相信大家已经跃跃欲试,想动手写...

    短短的路走走停停
  • 干货 | JAVA调用cplex求解一个TSP模型详解

    前面我们已经搭建好cplex的java环境了,详情可以看干货 | cplex介绍、下载和安装以及java环境配置和API简单说明,相信大家已经跃跃欲试,想动手写...

    用户1621951
  • 纸上谈兵: 拓扑排序

    《文明》是一款风靡20多年的回合制策略游戏,由Sid Meier开发。《文明》结构宏大,内容丰富,玩法多样,游戏性强,称得上是历史上最伟大的游戏。在文明中,你可...

    Vamei

扫码关注云+社区

领取腾讯云代金券