How to grok this badly written article on DFS?

Question

As someone who has not english as moms language (Russia) I read this article at Wikipedia: http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Depth-first_search

and I try to follow this pseudo code example written in hardcore english with less to nothing explanations or comments.

In particular, I don't get what they try to say with this sentence:

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

for all nodes v adjacent to u do

My problem with this sentence is the "adjacent" part. My dictionary says this means something like "neighbor". So I have to iterate over the subnodes of the supernode of u? Note that u is a node in the graph.

Or are they trying to say I must iterate over all the subnodes of u? Because this would make a huge difference.

Besides those english problems they forgot to mention what d and p mean, which makes me ripp all my hairs out (yes, even those from my mustache).

The links in the article just repeat this not-much-telling cryptic stuff. Maybe someone was able to actually re-write this in a way that is more humanly readable, with more comments and meaningful variables? I didn't find any really good explanation that isn't just there to show off the dominating intelligence of the writer related to DFS.

So if someone can re-write that on the fly in a better way with greater learning value that would save my day, save my mustache. Save everything. Thank you.

Konrad Garus · Answer 1 · 2011-04-26T10:05:22.047

2

It means: "For all nodes v directly connected to u".

Pseudocode in http://en.wikipedia.org/wiki/Depth-first_search is much simpler. Hope this one works better for you.

If I remember correctly, the d, p and f come from Cormen's book on algorithms. They mean (respectively) the moment the node was discovered, previous node on the DFS traversal tree and the moment the node was finished. Some of them are useful for some applications (such as topological sorting, finding components and other algorithms around DFS), but they're not crucial for DFS itself.

edited Apr 26 '11 at 10:05

answered Apr 26 '11 at 09:59

Konrad Garus

53,145
43
157
230

are you sure that you didn't mean "for all nodes v directly connected to u"? – Proud Member Apr 26 '11 at 10:00
I find that even worse. But I realized it doesn't help much anways because they do it with recursion. My DFS works already but I'm not able to track depth: http://stackoverflow.com/questions/5788299/how-to-track-the-depth-in-this-object-graph-depth-first-search-algorithm – Proud Member Apr 26 '11 at 10:10

score 2 · Answer 2 · edited May 23 '17 at 12:29

2

My code from a similar question might be helpful to you:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

dfs(t)

edited May 23 '17 at 12:29

Community

1
1

answered Apr 26 '11 at 14:42

RossFabricant

12,364
3
41
50

score 1 · Accepted Answer · answered Apr 26 '11 at 12:02

I would be a bit less reproachful when the language barrier is on your side.

Anyway, "adjacent" means directly connected. In this graph:

A is adjacent to B and C, B is adjacent to A, C is adjacent to A, E, and D, D is adjacent to C, and E is adjacent to C.

Here is the same code, a bit more verbose:

{with the following global variable:
    time, which is a single integer, and initially 0;}

{and a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;
    previous-node;
    discovery-time;
    finishing-time;}

{depth-first-search of node u is:
    visit the value of u;
    increase time by 1;
    set the discovery-time of u to time;
    set the colour of u to grey;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            set the previous-node of v to u;
            depth-first-search of v;}}

    increase time by 1;
    set the finishing-time of u to time;
    set the colour of u to black;}

There are several things in this code that serve purely illustrative purposes. The central theme is this:

{with a node being a structure of:
    value;
    adjacent-nodes;
    colour, initially white;}

{depth-first-search of node u is:
    visit the value of u;
    set the colour of u to black;

    {for all nodes v in the adjacent-nodes of u:
        {if the colour of v is white then:
            depth-first-search of v;}}}

Great. Exactly what I needed. A visual example! Thanks! – Proud Member Apr 26 '11 at 17:11 — Proud Member, Apr 26 '11 at 17:11

How to grok this badly written article on DFS?

3 Answers3