What is the best way to traverse all the vertices of a graph?

Question

Mathematics

It is necessary to go around all the vertices of an undirected connected graph, moving pointwise along the edges. The graph is arbitrary (not Euler and not Hamilton, except for connectivity, nothing is given). The transition along the edge is one step. How to do it in the minimum number of steps? Returning to the original vertex, as in the traveling salesman problem, is not necessarily the main thing to visit each vertex at least once.

Answer 1

Obviously, by traversing the graph .
Which of the algorithms is better to use and what modifications can be made depends on the specific features of the graph, that is, for an arbitrary one, it is not known in advance which variation will be the most optimal.
If possible, then you need to collect statistics and look at the possible features of the processed graphs. So, for example, for "stars" it will be optimal to bypass the center with BFS, after which the processing of rays using DFS.

Answer 2

If we talk about coins: this is finding the shortest path on which all the coins lie. I would use Dijkstra's algorithm .

Answer 3

For the number of vertices of the order of 15: (more than 15 vertices will work already relatively longer)

1. We run the floyd to get a matrix of 15x15 ways how to get from one vertex to another in the fastest way. Or 15 rounds in depth (same speed, same effect).
   
2. We sort through all the permutations of numbers from 1 to 15, which, as you know, are 15! = 1307674368000.
   
3. Using the matrix obtained in the first step, we consider the total number of steps that
   would have been obtained if we had followed the vertices in permutation order.