跃迁引擎

空気を読んだ雨降らないでよ

iOS Research & Development


判断图中是否存在环

使用「深度优先搜索」来判断图中是否存在回路,该题目出自 2018 年阿里巴巴手机淘宝 iOS 客户端架构组应届生面试题目。

Description

有一个包含 N 个顶点,M 条边的有向图,以及提供该图是无向图还是有向图,如果 I == 0 则是有向图,I == 1 则是无向图。

Input

N 表示顶点的个数,M 表示边的个数。I 表示是否为无向图,如果 I == 1 则是无向图,如果 I == 0 则是有向图。(0 < N <= 100, 0 < M <= 4000)。接下来 M 行代表边输入两个正整数 AB0 < A, B <= N)。代表有一条从 A 指向 B 的边。

Output

如果该图存在环,则输出字符串 Yes,否则输出 No

Sample Input 1

1
2
3
4
5
6
4 5 0
1 2
2 3
1 3
1 4
2 4

Sample Output 1

1
NO

Sample Input 2

1
2
3
4
3 3 1
1 2
1 3
2 3

Sample Output 2

1
Yes

Sample Input 3

1
2
3
3 2 1
1 2
2 3

Sample Output 3

1
No

这道题目出自 2018 年阿里巴巴手机淘宝 iOS 客户端架构组应届生面试题目。当时的场景是口术思路,并没有要求代码实现。

审题

先看一遍题目说明和要求,首先明确了3个变量:代表一张图中顶点数量的 N、代表边数量的 M 和 代表该图是有向图还是无向图的 I

其中 I 已被明确告知,当 I == 0 为有向图,I == 1 为无向图。

接下来是输入条件,这里又出现了2个变量,代表边方向起点的 A 和代表边方向终点的 B,也就是说,一条边的方向由 A 指向 B 来决定。

随后又给出了这5个变量的值区间:

  • 0 < N <= 100
  • 0 < M <= 4000
  • 0 < A, B <= N
  • I = 0 || 1

题目要求最后输出图中是否存在环的判断结果,如果该图存在环,则输出字符串 Yes,否则输出 No

那么这里的「环」究竟代表着什么意思呢?我们不妨先带着问题继续往下看。

分析

题中提供了三个输入样例供我们参考,分别都输入了一大串数字,这串数字又是什么意思呢?

我们先来观察一下三个样例中的数字,你是不是发现了什么规律?

没错,全部都是第一行3个数字,其余行2个数字,结合题目给出的输入要求,其实不难看出,第一行的三个数字,分别对应着 N,MI 的值,而下面行的左右分别对应着 AB 的值。这样再回过头去看这3个输入样例,就豁然开朗了。

这串数字代表的含义搞懂了,但是什么是「环」还没弄清楚,不要着急,你虽然不清楚什么是「环」,但是输入样例里已经有了「环」和「非环」的输出状态 YesNo 的区分,我们只需要按照样例输入的值画出图来,就能直观的用可视化的方式看出其中差异,找到判定为「环」的必要条件,Let’s go!

首先画出第一个输入样例所表示的图:
有向图

把图画出来之后,一目了然。这是一张有向图,第一个输入样例的输出结果是 No,表示图中不存在「环」,观察这张图,我们暂时先不做结论,继续画第二个样例的图:
无向图1

第二个样例画出来的是一张无向图,输出结果是 Yes,表示图中存在「环」,你应该已经看出了什么端倪,同样是不要着急做出结论,我们继续画完第三个样例:
无向图2

第三个样例还是一张无向图,输出结果是 No,标识图中不存在「环」。对比这三张向图,我们终于可以得出一个初步的结论,所谓的「环」,就是顶点之间连接的边产生了一条回路

特殊情况

但是,一定要所有顶点都连接成一条完整的回路才算做图中存在「环」吗?我们再来看看下面这几种特殊情况:

  1. 局部产生回路
    特殊情况1-局部环
    由于图内局部顶点之前形成回路,所以图中也存在「环」
  2. 自环
    特殊情况2-自环
    有向图 1 -> 1 或 无向图 1 - 1 这种应该也算「环」,称为自环。
  3. 有向图和无向图对于「环」定义的区别
    特殊情况3-有向无向区别
    对于有向图而言,「环」等于回路, (1) -> (2) 、(2) -> (1) 这个是「环」,但对于无向图来说 (1) - (2) 不是「环」。
  4. 有向图中的回路
    特殊情况4-有向图回路
    有向图里,产生「环」的必要条件是有一条完整回路,也就是从哪里来,还能回到哪里去,比如(1) -> (2), (2) -> (3), (3) -> (1) 算存在环,但是 (1) -> (2), (1) -> (3), (3) -> (2) 就不存在环,因为没有形成回路

明确了「环」产生的条件之后,我们就可以开始着手进行答题了。

最近的文章

我是如何快学上手 Sketch 的

如何在短时间内快速学习并掌握 Sketch 常用的基础操作,本文记录了我从 0 基础开始的学习过程与快速上手的使用技巧总结,希望能够对你有所帮助。 …

, , 开始阅读
更早的文章

斐波那契数列

用「动态规划」 「模拟」的思想,解决斐波那契数列,文中题目出自 LINE 的面试笔试算法题,难度中等偏上。 …

, , , , , 开始阅读
comments powered by Disqus