This problem is discussed in the book Algorithms in C++ volume 5 - Graph Algorithms. I believe your solution is going to be based on minimal spanning trees. The chapter on this topic (chap 20) is very detailed. I think if you can see it, then you will have more direction to go to solve your problem. I enjoy graph theory and wish I could answer more but I can't. I do own the book I referenced if you need some help.

Minimum spanning tree - Wikipedia[^]

16,020,666 members

thendo what I suggested, I think you'll find the same walk as if you applied my suggestion to the entire graph.