algorithm - Function of this graph pseudocode -


procedure explore(g; v) input: g = (v;e) graph; v 2 v output: visited(u) set true nodes u reachable v   visited(v) = true previsit(v) each edge (v; u) 2 e: if not visited(u): explore(u) postvisit(v) 

all pseudocode find 1 path right? nothing while backtracking if i'm not wrong?

it explores graph (it doesn't return path) - that's reachable starting vertex explored , have corresponding value in visited set (not vertices corresponding 1 of paths).

it moves on next edge while backtracking ... , postvisit.

so if we're @ a, has edges b, c , d, we'll start going b, then, when return a, we'll go c (if hasn't been visited already), , go d after return a 2nd time.

it's called depth-first search, in case wondering. wikipedia gives example of order in vertices explored in tree: (the numbers correspond visit order, start @ 1)

in above, you're not exploring vertices going down left (1-4), after 4 go 3 visit 5, 2 visit 6, , on, until 12 visited.

with regard previsit , postvisit - previsit happen when first vertex, postvisit happen after we've explored of it's children (and descendants in corresponding dfs tree). so, in above example, 1, previsit happen right @ start, post-visit happen @ end, because vertices children of 1 or descendants of children. order go like:

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


Comments

Popular posts from this blog

inversion of control - Autofac named registration constructor injection -

ios - Change Storyboard View using Seague -

verilog - Systemverilog dynamic casting issues -