I have a minimum spanning tree in Java.
This is in a Graph
class which has a list of Node
s, 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?
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.