Depth First Search

What is Graph?
A graph is just a set of vertices (nodes), together with edges (connections) between some pairs of nodes. If the connections have a direction, the graph is said to be “directed graph”, otherwise the graph is said to be “undirected graph”.

A graph G = (V, E) with V, i.e. set of vertices and E, i.e. set of edges.

Searching a graph: Systematically follow the edges of a graph to visit the vertices of the graph. And is used to discover the structure of a graph.

Standard graph searching algorithms are

• Depth First Search (DFS)
• Breadth First Search (BFS)

Problem Statement
Deeply search a graph to make logical tree. 
Depth First Search
Depth first is an algorithm for traversing or searching a tree. It explore edges out of the most recently discovered vertex v. When all edges of v have been explored, backtrack to explore other edges leaving the vertex from which v was discovered (its predecessor). 

 “Search as deep as possible first.”

Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree. 
Traversal continues until all vertices reachable from the original source are discovered. If any undiscovered vertices remain, then one of them is chosen as a new source and search is repeated from that source.

Input: G = (V, E), directed or undirected. No source vertex given!

Output:

• 2 timestamps on each vertex. Integers between 1 and 2|V|.
• d[v] = discovery time (v turns from white to gray)
• f [v] = finishing time (v turns from gray to black)
• π[v] : predecessor of v = u, such that v was discovered during the scan of u’s adjacency list.

Algorithm

The algorithm uses a global timestamp time.

Classification of edges
Tree edge (T): In the depth-first forest. Found by exploring (u, v).
Back edge (B): Those non-tree edges(u, v), where u is a descendant of v (in the depth-first tree). Self-loops are considered to be back edges.
Forward edge (F): Those non-tree edges(u, v), where v is a descendant of u, but not a tree edge.
Cross edge (C): Any other edge which can go between vertices in same depth-first tree or in different depth-first trees.

Note: In DFS of an undirected graph, we get only tree and back edges. No forward or cross edges.

Simulation
To illustrate the progress of Depth First Search, we use the following directed graph

To keep track of the progress, we color the vertices on following basis.

• White – Undiscovered
• Gray – Discovered but not finished
• Black – Finished

• On the execution of Line 1-4 of DFS(G), we get the following output. All vertices will be colored WHITE.

• On the execution of Line 5-7 of DFS(G) with u as vertex a, the if check is TRUE. So, on execution of Line 1-3 of DFS-VISIT(u) with u as vertex a, we get the following output.

• On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex a and v as vertex b, the if check on Line 5 is TRUE. So, the output will be

• On the execution of Line 1-3 of DFS-VISIT(u) with u as vertex b, we get the following output.

• On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex b and v as vertex d, the if check on Line 5 is TRUE. So, the output will be

• On the execution of Line1-3 of DFS-VISIT(u) with u as vertex d, we get the following output.
  

• On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex d and v as vertex c, the if check on Line 5 is TRUE. So, the output will be

 

•  On the execution of Line 1-3 of DFS-VISIT(u) with u as vertex c, we get the following output.

• On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex c and v as vertex e, the if check on Line 5 is TRUE. So, the output will be

• On the execution of Line 1-3 of DFS-VISIT(u) with u as vertex e, we get the following output.

 

• On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex e and v as vertex f, the if check on Line 5 is TRUE. So, the output will be

• On the execution of Line 1-3 of DFS-VISIT(u) with u as vertex f, we get the following output.

•  On the execution of Line 4-7 of DFS-VISIT(u) with u as vertex f and v as vertex d, the if check on Line 5 is FALSE, as the adjacent vertex d is not WHITE. So, the edge (f, d) is Back edge and the output will be

• On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex f, is colored BLACK.

• Recursively, on the execution of Line 4-7 of DFS-VISIT(u) with u as vertex e and v as vertex e, the if check on Line 5 is FALSE, as the adjacent vertex e is not WHITE. So, the edge (e, e) is Back edge and the output will be

•  On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex e, is colored BLACK.

• Recursively, on the execution of Line 4-7 of DFS-VISIT(u) with u as vertex c and v as vertex b, the if check on Line 5 is FALSE, as the adjacent vertex b is not WHITE. So, the edge (c, b) is Back edge and the output will be

• On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex c, is colored BLACK.
  

• Recursively, on the execution of Line 4-7 of DFS-VISIT(u) with u as vertex d and v as vertex e, the if check on Line 5 is FALSE, as the adjacent vertex e is not WHITE. So, the edge (d, e) is Forward edge and the output will be

• On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex d, is colored BLACK.

• Recursively, on the execution of Line 4-7 of DFS-VISIT(u) with u as vertex b and v as vertex e, the if check on Line 5 is FALSE, as the adjacent vertex e is not WHITE. So, the edge (b, e) is Forward edge and the output will be

• On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex b, is colored BLACK.

• On the execution of Line 8-9 of DFS-VISIT(u) with u as vertex a, is colored BLACK.

Parenthesis theorem
For all u, v, exactly one of the following holds:

1. d[u] < f [u] < d[v] < f [v] or d[v] < f [v] < d[u] < f [u] and neither u nor v is a descendant of the other.
2. d[u] < d[v] < f [v] < f [u] and v is a descendant of u.
3. d[v] < d[u] < f [u] < f [v] and u is a descendant of v.

By applying parenthesis theorem on above graph, we get

(a (b (d (c (e (f f) e) c) d) b) a)

Running time
Loops on lines 1-2 & 5-7 taketime, excluding time to execute DFS-Visit.

DFS-Visit is called once for each white vertexwhen it is painted gray the first time. Lines 3-6 of DFS-Visit is executed |Adj[v]| times. The total cost of executing DFS-Visit is.

Total running time of DFS is.

Comparative Analysis
As, standard graph searching algorithms are depth first search and breadth first search, so their comparison of running time is
Depth First Search                         
Breadth First Search                 O (V + E) 

Application – Maze
Maze is made by depth first search. Following maze is of factor 7

• Find your way through the maze by circling the numbers that are divisible by 7. But watch out for dead ends, which you can mark with an X.

• Solution: Numbers in gray squares are factors of 7 that result in dead ends. Numbers in white squares are not factors of 7.

• The numbers in black squares trace the path through the maze

Conclusion
Depth first search is more efficient than breadth first search, if implemented efficiently.

In depth-first search, you start at the root of the tree and then explore as far along each branch, then you backtrack to each subsequent parent node and traverse its children. Usually, a depth-first-search is a way of iterating through an actual graph/tree structure looking for a value, whereas backtracking is iterating through a problem space looking for a solution



Feel free to comment with your questions and suggestions regarding the post content...!