Depth First Search

Question

Perform Depth-first Search on the graph shown starting with vertex a. When you traverse the neighbours, process them in alphabetical order.

The question is to find the DFI, Level and the Parent of each vertex.

Here is a picture of it:

I'm unsure of how to get going with this, it is a practice question for an upcoming exam. I know for depth first search, it uses a stack and it will start at vertex a and go in alphabetical order in the stack but i'm not sure how I would get the values for each of the columns. Can someone explain further or help me with this?

Answer 1

So you start at 'a' and must traverse the nodes in alphabetical order so from a you either have the option of going to b or g so you choose b because it is first alphabetically. from b your only choice is g and so on....

now for your values. the parent of a is null since you have no previous nodes the parent of b is a and the parent of g is b and so on.

the dfs level is the level that it would end up on a tree. so imagine that you do your traversal then erase all lines that weren't part of the traversal. and then you take your root and 'shake it out' what i mean is you rearrange it so that it looks like a tree. (this particular graph is very uninteresting) and then you assign levels based on that tree.

And the dfs index is simply the order in which you touched the nodes.

The folowing are for your graph but using g as a starting point....I think it makes it slightly more intersting

the numbers are the order in which the edges were taken.

Here is what i was talking about when i said 'shake it out' this is what your tree looks like and in blue i show the level of each node(0 based). I hope the images make it a little more understandable.

the one i drew( the terrible free hand one) was formed by deleting all of the edges that weren't used and then rearranging them to look like a tree.

You can think of the depth as how many steps did i have to take from the root to get to the current node. so from g to b is 1 step so depth of 1 from g to i 3 because we go from g->c->d->i 3 steps. after you have made your traversal you ignore the fact that you can in fact get from g to i in two steps(g->h->i) because it wasnt part of the traversal

Answer 2

The index is simply the number in order that the node is visited. a is first, write 1 there. Knowing depth first search as you do, you should know what the second node is; so write 2 under that. Depth is how high a node is; every time you deepen the depth, it increases, and whenever you go shallower, it's less. So a is on depth 1; the next node and its sister will be on depth 2, etc. The parent is the letter identifying the node that you just came from; so a has no parent, and the node with index 2 will have a as parent.

If your class uses a zero-based numbering system, replace 2 in the above paragraph with 1, and 1 with 0. If you have no idea what "zero-based numbering system" is, ignore this paragraph.