# Find the spanning tree minimizing the backtracking in an unweighted graph

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.

The problem is NP-hard since the graph admits a spanning tree with no backtracking if and only if it contains a Hamiltonian path. This shows that, if the measure to optimize is the number of times you backtrack, then there can be no polynomial-time approximation algorithm unless $$P \neq NP$$.
If the measure is the number of moves needed to visit all the vertices while moving along the edges of the tree, then an arbitrary spanning tree already provides a $$2$$-approximation. Indeed, any solution must involve at least $$n-1$$ moves, while an Eulerian tour of a spanning tree traverses each of the $$n-1$$ edges twice.
Unfortunately, this means the complexity is $$O(n^22^n+n^3)$$ at best (when using a dynamic programming approach).