CODEWITHSUNDEEP
algorithmgraphpseudocodedepth-first-search
Dubby
Dubby

Reputation: 1144

Function of this graph pseudocode

procedure explore(G; v)
Input: G = (V;E) is a graph; v 2 V
Output: visited(u) is set to true for all nodes u reachable from v


visited(v) = true
previsit(v)
for each edge (v; u) 2 E:
if not visited(u): explore(u)
postvisit(v)

All this pseudocode does is find one path right? It does nothing while backtracking if I'm not wrong?

Upvotes: 0

Views: 505

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

It just explores the graph (it doesn't return a path) - everything that's reachable from the starting vertex will be explored and have the corresponding value in visited set (not just the vertices corresponding to one of the paths).

It moves on to the next edge while backtracking ... and it does postvisit.

So if we're at a, which has edges to b, c and d, we'll start by going to b, then, when we eventually return to a, we'll then go to c (if it hasn't been visited already), and then we will similarly go to d after return to a for the 2nd time.

It's called depth-first search, in case you were wondering. Wikipedia also gives an example of the order in which vertices will get explored in a tree: (the numbers correspond to the visit order, we start at 1)

In the above, you're not just exploring the vertices going down the left (1-4), but after 4 you go back to 3 to visit 5, then back to 2 to visit 6, and so on, until all 12 are visited.

With regard to previsit and postvisit - previsit will happen when we first get to a vertex, postvisit will happen after we've explored all of it's children (and their descendants in the corresponding DFS tree). So, in the above example, for 1, previsit will happen right at the start, but post-visit will happen only at the very end, because all the vertices are children of 1 or descendants of those children. The order will go something like:

pre 1, pre 2, pre 3, pre 4, post 4, pre 5, post 5, post 3, pre 6, post 6, post 2, ...

Upvotes: 1

Related Questions