data-structures - 什么是无环连通无向图？

Question

我正在通过最小生成树的讲座，它说我们应该在无向图中找到连接的无环子图。

我的问题是，连接的无向图如何是无环的，因为它是连接的，您可以从任何顶点移动到任何顶点。

谁能告诉我我做错了什么？

Answer 1

这实际上只是一个定义问题。请参阅http://en.wikipedia.org/wiki/Cycle_(graph_theory)。您似乎将其称为循环，在文章中称为封闭行走：从顶点到自身的任何路径。正如您自己所说，使用该定义，任何连接的无向图都包含循环。但是，如果您要求从第二个到最后一个顶点的子路径是一条简单路径（因此是简单的循环），即不包含重复顶点的路径，那么您最终会得到许多实际上是无环的连接无向图，例如树实例。显然，路径还必须包含至少 3 条边，否则任何(A,B,A)一条边都是循环。

考虑以下图表

     A         A
1)  / \   2)  / \
   B   C     B - C

只2)包含简单的循环，所以1)是非循环的。