CODEWITHSUNDEEP
javarecursionmatrixpathdepth-first-search
user3194972
user3194972

Reputation: 155

Finding a single path in a graph using dfs

I am currently trying to find a single path in a graph leading from source to sink. I am trying to implement a method using dfs to achieve this. However, i can't seem to figure out how to make the method to stop the recursion. For example, i have this graph (in matrix form)

0 1 1 0

0 0 0 1

0 0 0 1

0 0 0 0

So i have an edge from node 0 (the source) to node 1 and 2 respectively, and then an edge from 1 and 2 leading to 3 (the sink). The path i would want to have would be 0>1>3, instead i'm getting 0>1>3>2>3. How can i make the recursion stop as soon as a path to the sink is found?

Here is the code for the method:

public void dfsPath(int i) {

    boolean[] visited = new boolean[this.edgeCapacities.length];
    visited[i] = true;
    this.path.add(i); //Integer ArrayList containing the nodes in the path

            //loop through all of the nodes in the matrix to find adjacency
            for (int j = 0; j < this.edgeCapacities.length; j++) {
                //check if edge exists and node has not been visited
                if (this.edgeCapacities[i][j] != 0 && !visited[j]) {
                    //here is the problem, i want the recursion to stop once the sink is found
                    //it does not work however.
                    if(j == this.sink) {
                        visited[j] = true;
                        this.path.add(j);
                        return;
                    } else {
                        //recursion
                        dfsPath(j);
                    }
                }
        }

Any help would be greatly appreciated. Thanks in advance.

Upvotes: 1

Views: 2883

Answers (1)

tobias_k
tobias_k

Reputation: 82889

There seem to be several problems with your DFS algorithm:

  • by creating a new visited list in each recursive call, it always contains only the current node
  • you are only adding nodes to this.path, but never removing nodes that did not lead to the goal
  • you never check whether one of your recursive calls reached the goal, thus adding more nodes to a perfectly good path

To fix this, you should remove the current node from this.path at the end of the method, i.e. in case no path has been found. Also, you can just drop the visited array and just check whether the next node is already in the path. That's not quite as fast, but should suffice for your case and make the code less complex. Also, the method should return true or false depending on whether it found a path.

Try this (not tested, but should work).

public boolean dfsPath(int i) {
    this.path.add(i); // add current node to path
    if (i == this.sink) {
        return true; // if current node is sink, return true
                     // this.path contains nodes from source to sink
    }
    for (int j = 0; j < this.edgeCapacities.length; j++) {
        if (this.edgeCapacities[i][j] != 0 && ! this.path.contains(j)) {
            if (dfsPath(j)) {
                return true; // found a path -> search no further
            }
        }
    }
    this.path.remove(this.path.size() - 1); // pop last node
    return false; // no path found
}

Note that I also moved the sink-check out of the loop. This is purely a matter of taste, but it makes the code a bit simpler, as you don't have to add the sink node separately to the path.

Upvotes: 1

Related Questions