how to print all possible graph combinations

Suppose that we set the number of vertices in a graph as n. (we can set this by user inputs etc.)

I'd like to print all possible cases of connecting vertices using edges. (So, I'd like to print all possible (simple) connected graphs of n vertices.)

Also, for each case, I'd like to print degree of each vertex in each case.

---

A naive but simple solution would be to create all possible graphs, and filtering out the not connected ones.

Create a set of all possible edges. There are n(n-1)/2 of those, and this will be the set's size.

Find the power set of the required set. This power set represents all possible graphs that can be created.

The wikipedia article also gives an algorithm for calculating the power set of a set. This post also discusses this issue (java)

For each subset created - check if it is connected or not. it can be done using a discovery algorithm such as BFS. The graph is connected if and only if BFS discovered all vertices, when starting from a single (random) source.

链接地址: http://www.djcxy.com/p/37310.html

上一篇: 与相关顶点成本相关的二分选择

下一篇: 如何打印所有可能的图形组合