detect cycle in DFS

martingalemsy 发表于 2021-6-30 02:17
感谢回复，我演练了一下你说的菱形的栗子感觉用这个代码是可以判断的呀，当扫到最下面的节点D时，已经到 ...

嗯……LZ的findCycle是如果找到cycle就返回true，没找到返回false吧？
假设有一个三角形，三个顶点标号1、2、3，三条有向边构成一个cycle，
即：1->2->3->1
那LZ的代码返回false，代表acyclic吧？

您好楼主，我看其他答主的答案都很完善了，想提供另外一种思路。
其实cycle detection 可以用BFS-based topological sort来实现。

对图跑一遍topological sort然后看遍历的节点数量是否等于图的节点数量。

https://www.geeksforgeeks.org/de ... ed-graph-using-bfs/