CODEWITHSUNDEEP
javaalgorithmrecursiondepth-first-search
spogebob92
spogebob92

Reputation: 1484

Depth first search in java - how to go back to parent node?

I'm trying to do a depth first search in Java recursively. At the moment, the code runs through my graph fine, but it never backtracks to find a route when they're are no more nodes to visit. I'm having a bit of a mental block honestly. What would be the best way to go back to the parent node?

Here is my code so far:

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;

public DepthFirstSearch(Graph graph){
    mNodes = graph.getNodes();
    mEdges = new ArrayList<>(graph.getEdges());
    for(Node node : mNodes.values()){
        node.setVisited(false);
    }
}

public void depthFirstSearch(Node source){
    source.setVisited(true);
    List<Node> neighbours = source.getNeighbours(mEdges);
    for(Node node : neighbours){
            if(!node.isVisited()){
                System.out.println(node.getName());
                depthFirstSearch(node);
            }
        }
    }

And the getNeighbour code:

public List<Node> getNeighbours(List<Edge> edges) {
        List<Node> neighbours = new ArrayList<>();
        for(Edge edge : edges){
            if(edge.getFrom().equals(this)){
                neighbours.add(edge.getTo());
            }
        }
        return neighbours;
    }

Added code for trying Jager's idea:

public void depthFirstSearch(Node source){
        source.setVisited(true);
        List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
        for(Edge edge : neighbours){
                if(!edge.getTo().isVisited()){
                    System.out.println(edge.getTo().getName());
                    depthFirstSearch(edge.getTo());
                }else{
                    depthFirstSearch(edge.getFrom());
                }
            }
        }

Upvotes: 1

Views: 1667

Answers (2)

Aconcagua
Aconcagua

Reputation: 25526

Well, typically you have a root node that has children. Each child can have children of its own. So you would rather do:

public void depthFirstSearch(Node source)
{
    for(Node node : source.getChildren())
    {
        System.out.println(node.getName());
        depthFirstSearch(node);
        // and right here you get your back tracking implicitly:
        System.out.println("back at " + node.getName());
    }
}

Note that I do not have a necessity for a member visited...

Edit:

Now that you provided your data structure, let me propose another approach:

class Node
{
    // all that you have so far...

    private char mId;
    private List<Node> mChildren = new ArrayList<Node>();

    public char getId()
    {
        return mId;
    }
    public List<Node> getChildren()
    {
        return Collections.unmodifiableList(children);
    }

    // appropriate methods to add new children
}

The id replaces the key of your map. Then you simply have a root Node mRoot to start with somewhere. This is the typical way to implement trees.

You might want to go up from a child node directly. Then you'd additionally need a private Node parent; in the node class (immediately being set to this when adding a child to the private list and set to null, when being removed). You won't use this for backtracking, though, so the depth first search above remains unchanged.

Upvotes: 2

GhostCat
GhostCat

Reputation: 140447

Guessing: you are "getting" the neighbors for mEdges which seems to be a field of the surrounding class.

Most likely, you should ask each node for its own edges upon visiting it.

Upvotes: 0

Related Questions