Computing using depth-first-search (DFS)

Problem:

In class today, we learn about a computing method for traversing a graph (see Presentation #2, slide #9), called depth-first-search (DFS).

(a) Can you write up a recursive computing procedure for doing so?

(b) Can you analyze its estimated running time?

(c) Can you name some “everyday computing” applications of this method?

Follow-Up:

(a) A possible recursive algorithm is as follows:

DFS(x):

1. Mark x;
2. For every neighbor y of x that is not marked:
3. DFS(y);

(b) As discussed in class, the DFS procedure visits each and every node once, also each and every link once. Thus, the estimated running time should be on the order of N + E , where N and E are the number of nodes and number of links, respectively.

(c) We need to use DFS for many useful daily life applications:

• playing chess: searching for the best move in the game tree;
• playing puzzle: searching for the exit in a maze;
• crawling the Web: the crawler program (e.g., in Google) needs to search the Web graph (i.e., visualizing the Web as a graph of connected documents, where the connections are the hyper-links) in a depth-first way.