algorithm - 具有 n 个顶点的图 - 如何打印所有可能的图组合

Question

假设我们将图中的顶点数设置为 n。（我们可以通过用户输入等来设置它。）

我想打印使用边连接顶点的所有可能情况。（所以，我想打印所有可能的（简单的）n 个顶点的连接图。）

另外，对于每种情况，我想在每种情况下打印每个顶点的度数。

Answer 1

一个天真的但简单的解决方案是创建所有可能的图形，并过滤掉未连接的图形。

创建一组所有可能的边。有n(n-1)/2这些，这将是集合的大小。

找到所需集合的幂集。这个幂集代表了所有可以创建的图。

维基百科文章还提供了一种计算集合的幂集的算法。这篇文章也讨论了这个问题（java）

对于创建的每个子集 - 检查它是否已连接。它可以使用诸如BFS之类的发现算法来完成。当且仅当 BFS 从单个（随机）源开始时发现所有顶点时，图才连接。