c++ - 如何仅使用邻接表在无向图中找到存在的循环（顶点也没有）？

Question

如果你只有一个邻接矩阵，你如何找到无向图中的循环在哪里？

标签： c++algorithmgraph-theoryadjacency-matrixgraph-traversal

Answer 1

要在无向图中查找循环，您需要在该图上运行深度优先搜索 (DFS)。如果您的图表示为邻接矩阵，则其运行时间为 Θ(V+E)，其中 V 是顶点数，E 是边数。运行 DFS 时，您需要将遍历的每条边分类为树边或后边. 如果在处理 (u, v) 之前未看到 v，则顶点 u 和 v 之间的边（表示为 (u, v)）是树边。如果在处理 (u, v) 之前已经发现 v，则 (u, v) 是后边。后边的发现表明图中存在一个循环，因为存在一条从一条边离开顶点并从另一边返回到同一顶点的路径。一旦你对所有边进行了分类，任何后边 (u, v) 都会与形成从 u 到 v 的路径的树边形成一个循环。