How to convert a minimum spanning tree to a path/route in Java?

Issue

I have a minimum spanning tree in Java.
This is in a Graph class which has a list of Nodes, those Node classes have a list of Edge classes which have a boolean if they are in the MST or not.
Example:

In this example a human can see that a path/route to go to all the places and back from the start is: (Start-A --> A-Start --> Start-B --> B-C --> C-B --> B-D --> D-B --> B-Start), how can I code this route to a String, only knowing which connections to use and the start?

Solution

This problem can be solved using DFS for trees.
It could be useful to look at the tree by using Start as a root.
Imagine that from node Start we go to node A. We add this movement to our path string. Now two possibilities can materialize: the first is that A has no child, so we go back to Start and we have to print the inverse of the movement done before; the second is that A has one or more children, in which case we do a movement to reach the first child (update the string). When we have finished exploring the "depth" of this child we'll go back to A and start with another child (if it's present).

Probably, it's more difficult to explain this in words than seeing this in code: the key concept here is that when we finish exploring the depth of a possible path we have to get back to the node from which it started (which corresponds only to adding the inverse of the movement string in the parent).

public void dfs(Node u, Node previous, StringBuilder path) {
        for(Edge e: u.edges) {
            // an edge is a pair (e.a, e.b)
            if(!e.mst || e.b.equals(previous)) {
                continue;
            }
            path.append(u + "->" + e.b + "\n");
            dfs(e.b, u, path);
            path.append(e.b + "->" + u + "\n"); // after exploring a child we must get back
        }
    }

This is the code example that you can adapt to your use case.

Answered By - Nicola