Traverse through a networkx graph covering all nodes

I want to traverse through all the nodes in an undirected networkx graph given a start node. The order of nodes visited is not a concern as long as it finds a optimal path with few nodes repeated.

Example:

G = nx.Graph(4)
G.add_edges_from([(1,2),(2,3),(2,4)])

The returned optimal answer:

[1,2,3,2,4] # for start node 1
[3,2,1,2,4] # or [3,2,4,2,1] for start node 3

Thanks in advance

The optimal answer, with no vertices revisited and no edges traversed more than once, is called the travelling salesman problem. It is a very hard problem!

Since you are allowing revisited vertices and multiple edge traversals, there are various approximations that can be used to get such answers in a reasonable amount of processing time.

The general idea is to find the minimum spanning tree and do a depth first search through the tree, allowing backtracking when necessary - a leaf of the tree is reached.

Without more details about the particular problem you need to solve, I cannot be more specific. You should probably edit your question to provide some details.

However, one thing you should look into is: Is your graph "metric"? That is, for every possible triplet of vertices ( A,B,C ) is is ALWAYS cheaper to take the edge between two nodes rather than go via the third node. If it is, then you can use the metric approximate solution to the TSP. Note that most graphs that model real world problems will be metric, and the approximation is good enough for most uses. In your case, the edges seem to have no associated weights, so the assumption is that all edges have the same weight. That means that your graph is indeed metric and you should explore the approximate solutions to TSP. You could start with: http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf