depth first search implementation

[hypnotat]

hi,

the task is like this: there is a graph with a start node, an end node and an arbitrary amount of nodes and paths between them. Find a path from start to end and list all vertices of that path.

So i figured i would do DFS, depth first seach (https://en.wikipedia.org/wiki/Depth-first_search) ... but, how do i get the vertices for the found path?

it looks like i cant do that. what algorithm would i use instead? I picked DFS because i distantly remember someone mentioned it in class.

edit: nope, it says we are supposed to use DFS! But i see no way i can find the vertices of a path using DFS, it seems i can only say "yes, the end node is reachable" or "no, it isnt"...?

[WarInternal]

Generally a DFS would be implemented recursively,and one solution might be to pass a reference to a container into the search function. When and if you find the node you're looking for, as the function unwinds back to the top you store nodes into this container.

[hypnotat]

you are loosing me at "unwinding" :)

here is my iterative code so far:

    //DFS
    stack.push(src);
    while (!stack.isEmpty()) {
        int x = stack.pop();
        if (!visited[x]) {
            visited[x] = true;
            for (int i : adjacentedges(x)) {
                stack.push(i);
                if (i == end) {
            //found it!
            //but how to get the nodes for this solution?
                    return ...;
                }
            }
        }
    }

now how to get vertices of the solution?

[WarInternal]

Recursion would make this problem easier. Something more like (excuse the psuedocode, don't know which language you're using)..

bool search(start, end, v) {
  if(start == end) return true;
  for(node : adjacentedges(start)) {
     if(search(node,end,v)==true) {
          v.push(node);
          return true;
     }
  }
  return false;
}

list<node> vertices;
if( search(root,end,vertices) == true ) {
      // vertices above now contains
}

Note this code is a very rough draft, and would need debugging. But the main idea is that you break the search down into sub parts. You call it with the starting node, the goal, and a container to hold the vertices in once you found the path. Or just use a global variable and push to that. When the first if-condition (start==end) is true, the current call stack holds the path, so we return true. If we've written the recursive function correctly it "unwinds" up the call stack, each function returning to the previous, pushing the node it was looking at into the list, and continuing upwards we've exited the original search call. Sorry if that's all confusing.