Depth First Traversal and Breadth First Traversal

Depth First Traversal

Depth First Search (DFS)is also called depth first search. The essential feature of DFT is that when a node is visited, all descendent of the node are visited before its unvisited brothers. It traverses a single path of the graph as far as it can go until it visits a node with no successor or a node all of whose successors have already been visited.

In this traversal method,One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Algorithm:

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered

A recursive implementation of DFS:

procedure DFS(G,v):

label v as discovered

for all edges from v to w in G.adjacentEdges(v) do

if vertex w is not labeled as discovered then

recursively call DFS(G,w)

A non-recursive implementation of DFS:

procedure DFS-iterative(G,v):

let S be a stack

S.push(v)

while S is not empty

v = S.pop()

if v is not labeled as discovered:

label v as discovered

for all edges from v to w in G.adjacentEdges(v) do

S.push(w)

Example
For the graph below:

A depth first search strategy starts at A, assumingthat the left edges in the graph are chosen before right edges, and thatthe search remembers previously visited nodes and hence, will not repeat them (since this is a small graph). Thus the algorithm will visit the nodes in the following order:

A, B, D, F, E, C, G.

The edges traversed in this search form a tree.

The two variations of DFS visit the neighbors of each vertex in the opposite order from each other:the first neighbor of v visited followingthe recursive algorithmis the first one in the list of adjacent edges, while in the iterative method,the first visited neighbor is the last one in the list of adjacent edges. The recursive implementation will visit the nodes from the example graph above in the following order: A, B, D, F, E, C, G while the non-recursive implementation will visit the nodes as: A, E, F, B, D, C, G.

Example 2:

Applications

• Finding connected components
• Topological sorting
• Finding the bridges of a graph
• Planarity testing
• Maze generation and solving

Breadth First Traversal

Breadth First Traversal (BFS) is also called Breadth FIrst Search. It is implemented using a queue. In BFT, the general method is: Visit all successor of a visited node before visiting any successor of any of those successor.

It starts at the root of the tree(or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors, i.e. at first all the nodes in the same level are covered before moving to the next level of the graph.

Algorithm

Input: A graph Graph and a starting vertex root of Graph

Output: All vertices reachable from root labeled as explored.

A non-recursive implementation of breadth-first search:

Example 1:

Applications

• Copying garbage collection
• Finding the shortest path between two nodes u and v
• Computing the maximum flow in a flow network

References:

1.https://en.wikipedia.org/wiki/Depth-first_search

2.https://en.wikipedia.org/wiki/Breadth-first_search

2. Karumanchi, N. "Data Structures and Algorithms Made Easy"

3. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”