CODEWITHSUNDEEP
algorithmgraph-algorithm
user1441174
user1441174

Reputation: 47

A graph with n vertexes- 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.

Upvotes: 1

Views: 2912

Answers (1)

amit
amit

Reputation: 178491

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.

Upvotes: 1

Related Questions