Java中如何检测无向图和有向图中的环？

本文共计967个文字，预计阅读时间需要4分钟。

无向环+一个包含环的无向图如下所示，其中有两个环：+0-2-1-0+ 和 +2-3-4-2+：要检测无向图中的环，可以使用深度优先搜索。假设从顶点+0+出发，先扩展到顶点+2+，再连接到顶点+3+，接着到顶点+4+，最后回到顶点+2+。

无向环

一个含有环的无向图如下所示，其中有两个环，分别是 0-2-1-0 和 2-3-4-2：

要检测无向图中的环，可以使用深度优先搜索。假设从顶点 0 出发，再走到相邻的顶点 2，接着走到顶点 2 相邻的顶点 1，由于顶点 0 和顶点 1 相邻，并且顶点 0 被标记过了，说明我们饶了一圈，所以无向图中存在环。虽然顶点 2 和顶点 1 相邻，但是并不能说明存在环，因为我们就是从顶点 2 直接走到顶点 1 的，这二者只有边的关系。