I am working with undirected unweighted graphs, and I am searching for an algorithm that gives me a spanning tree minimizing the number of moves to visit every nodes.
For example, given this graph :
one spanning tree may be :
but, starting at a
, 11 moves are necessary to go through every nodes : ab
, ba
, ah
, hg
, gh
, hi
, ic
, cd
, dc
, cf
, fe
(note that getting back to the start is not required). But with another tree such as this one :
only 8 moves are necessary (which is incidentally the lowest possible for a graph with 9 nodes, but this is not attainable in every graph e.g. if there are multiple "dead-ends").
I am looking for an algorithm which could output such a tree (or path), or at least a good approximation. The graphs I am working with may have up to 100 nodes.
One of my ideas was to generate every spanning tree and then find the best one, but I don't know how to do it, and the number of trees may grow too fast for this to be practical.