数据结构 - 判断有向图是否存在回路,利用什么方法最佳?

问题描述

问 题

为什么这个题的答案是拓扑排序呢，而不是DFS呢?

如果我来写dfs判断是否有环存在, 就用一个数组来保存所有顶点是否被访问,如果在dfs过程中出现被访问的顶点再次被访问到就说明存在环.

---

我看到这个题目的出题人让我从时间复杂度的角度考虑...

我在一个算法群里面也问了这个问题, 然后群内的回复说是由于DFS会有回溯, 子节点在搜索完成后要回溯到前面的节点处,这里会多耗费时间.

解决方案

拓扑排序实质上是在标准DFS的基础上做了一些小改动从而得到图的一个线性序列。

你也许发现了，DFS的实现是多种多样的

• 有的实现对每个顶点标记状态（未发现、发现、已访问）（用于标记边的种类）

• 有的实现对每个顶点在标记状态的同时，还要标记发现时间点及访问结束时间点（用于实现拓扑排序）

• 有的实现则什么都不需要标记，但需要记录顶点间的父子关系（用于构造出深度搜索树）

相对于上面介绍的各种实现方式，这里标准DFS的意思是以深度搜索的方式访问/遍历图中的所有顶点，且只访问一次（并不干其他的事）。

个人觉得，答拓扑没问题。如果答DFS的话，我还会在说上一句：在DFS的基础上，标记遍历到的各个边的类型，一旦发现回边即可判定该有向图有环存在

这篇关于数据结构 - 判断有向图是否存在回路,利用什么方法最佳?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！