Is sounds like you want to generate a spanning tree of the graph, this is most commonly done with a depth-first or breadth-first search. Wikipedia has a short discussion of possibilities if you want to parallelise things.
Adding the consideration of weights, what you want is a minimum spanning tree, for algorithms, see, again, wikipedia.
Edit: As a good comment points out, the problem is not, given by finding a minimum spanning tree. It might still be a reasonable way to get a passable solution though.
Even finding out whether there is a solution at all is NP-complete. I will show this by reducing from 3SAT.
Given a 3SAT instance, create a copy of the following 18-node network for each 3-literal clause:
The edges $Y_1\leftrightarrow Z_1$, $Y_2\leftrightarrow Z_2$, and $Y_3\leftrightarrow Z_3$ represent the literal; the connections to the $Y_i$ and $Z_i$ nodes will be made later.
The nodes $A, B, C, D, E, F$ must be visited in that order. The edge going to the right from $F$ connects to the $A$ of the next clause.
The part of the path that visits $ABCDEF$ must use at least one of the $Y_i\leftrightarrow Z_i$ edges. Because $C$ must be visited, at least two of $X_1 X_2 X_3$ must be visited by this part of the path; this prevents any part of the path outside $ABCDEF$ from entering the $BCX_1X_2X_3$ network. (The rules imply that a node of degree $\le 3$ can be used at most once). Similarly on the other side of the fragment, no part of the path outside $ABCDEF$ can enter the $W_1W_2W_3DE$ network.
In addition to these clause networks, for each variable $x_n$ in the 3SAT problem have nodes $P_n, Q_n$ that must be visited in this order. Add a path from $P_n$ to $Q_n$ that passes through all the $Y_iZ_i$ edges for $x_i$ literals (connecting each $Z_i$ to the $Y_i$ of the next instance of $x_i$), and another path from $P_n$ to $Q_n$ that passes through all of the $\neg x_i$ literals. Because the $X_i$ and $Y_i$ nodes are not available outside the $ABCDEF$ segments, these two full paths will be the only ways to get from $P_n$ to $Q_n$.
Finally add connecting edges from each $Q_n$ to $P_{n+1}$, from the last $F$ to $P_1$, etc.
Now a path that passes through everything in order and does not reuse edges will correspond to a satisfying truth assignment, with each variable's truth variable determined by the path from $P_n$ to $Q_n$ we don't take. And in each clause there must be at least one of the literals that have the right truth value.
Best Answer
Create a graph with only the nodes of interest, and calculate for each pair the shortest distance (there are polynomial procedures for calculating the transitive closure of a graph).
Now you're looking for a relaxed version of the Traveling Salesman Problem.
Therefore, in this modified version, you can at least find an approximation algorithm using the MST of the modified graph with a factor of 2x (i.e. it is, at worst, twice as bad as the optimal route).
I'm not 100% sure, but I think the relaxed version of TSP was NP-complete as well, so searching for anything better than an approximation algorithm would be out of reach.
Either way, with this modification done, you can use everything we know about the TSP and apply it onto it.