Modified Search Problem: Find Path

Idea: To produce a path for each vertex, keep track of the vertex from which it was explored during the BFS/DFS process.

The demo here uses BFS, but we could do the same with DFS!

The following pseudocode describes the BFS algorithm.

// Pre: "s" is the source vertex
explored = {}
explored[s] = true 
queue.enqueue(s)
while (!queue.empty())
    v = queue.dequeue()
    for (w in adjacency[v])
        if (!explored[w])
            explored[w] = true    
            queue.enqueue(w)

Exercise Modify it to include and update the previous collection according to the demo.

previous = {}
explored = {}
explored[s] = true 
queue.enqueue(s)
while (!queue.empty())
    v = queue.dequeue()
    for (w in adjacency[v])
        if (!explored[w])
            explored[w] = true    
            queue.enqueue(w)
            previous[w] = v

Exercise Assuming the modified BFS produced the previous collection. Use previous to print out a path from the source to any given vertex.

// Pre: target is reachable from source
node = target
stack.push(node)
while (node != source)
   node = previous[node]
   stack.push(node)

print stack