Home > Software design >  DFS algorithm with target node
DFS algorithm with target node

Time:01-05

I have to use DFS algorithm for my university project. I saw this link DFSlink but i face this problem. The Depth First Search algorithm is Traversal it goes to every node in the graph but i want to define a target node when i reach to it i want to stop the algorithm

while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    if (n == goal) {
                        System.err.print(infoLinkedList.get(1).nameStation ":");
                        System.err.print(" |" goal  "| -> ");
                        return;
                    }
                    DFSUtil_BUS(n, goal, visited);
                }
            } 

How can i do this please?

CodePudding user response:

in this modified DFS, u also pass the target you want to check so if you have reached your desired target. you simply return

void DFS(int vertex, int target) {
    visited[vertex] = true; 
    System.out.print(vertex   " ");  
  
    Iterator<Integer> it = adj[vertex].listIterator();  
    while (it.hasNext()) {  
        int n = it.next();  
        if (!visited[n]) {
            if (n == target) {
                //return when u  reach the target
                return;
            }
            DFS(n, target);  
        }
    }  
}

CodePudding user response:

You don't actually terminate the search. All you do is call the DFS recursively if the current node has not been visited. Then, regardless of whether you found your target or not, you look at the next node.

You need to add a termination into the iterator. The first thing I would do is give the DFS function a return value: return true if the target has been reached, and false if not. Then, in your loop, break out of the loop if the return value is true, and return that from the current run. At the end of the while-loop, return false by default, as you have not found the target.

Update: You have now completely changed the question. My answer applies to the first version of it.

  • Related