Depth first search, Data Structure & Algorithms

Assignment Help:

DEPTH FIRST SEARCH (DFS)

The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisited vertices and whenever an unvisited vertex is not determined, it backtracks to earlier vertex to find out whether there are yet unvisited vertices.

As seen, the search described above is inherently recursive. We can determine a very simple recursive process to visit the vertices within a depth first search. The DFS is more or less alike to pre-order tree traversal. The procedure can be described as below:

Begun from any vertex (source) in the graph and mark it visited. Determine vertex that is adjacent to the source and not earlier visited via adjacency matrix & mark it visited. Repeat this procedure for all vertices that is not visited, if vertex is determined visited in this procedure, then return to the earlier step and begin the same process from there.

If returning back toward source is not possible, then DFS from the originally chosen source is complete and begin DFS using any unvisited vertex.

1686_DEPTH FIRST SEARCH.png

Figure: A Digraph

Let the digraph of Figure. Begun with S and mark it visited. Then visit the next vertex A, after that C & then D and finally E. Now there are no adjacent vertices of E to be visited next. Thus, now, backtrack to earlier vertex D as it also has no unvisited vertex. Now backtrack to C, then A, finally to S. Now S has an unvisited vertex B.

Begun DFS with B as a root node and then visit F. Now all of the nodes of the graph are visited.

Figure shows a DFS tree with a sequence of visits. The first number mention the time at which the vertex is visited first and the second number mention the time upon which the vertex is visited throughout back tracking.

386_DEPTH FIRST SEARCH1.png

Figure: DFS tree of digraph of above figure

The DFS forest is illustrated with shaded arrow in  above Figure.


Related Discussions:- Depth first search

Quick sort, This is the most extensively used internal sorting algorithm. I...

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Explain about greedy technique, Explain about greedy technique The  gre...

Explain about greedy technique The  greedy  method  suggests  constructing  a   solution  to  an  optimization  problem   by  a sequence of steps, every expanding a partially c

Basic concept of the primitive data structures, Q. Explain the basic concep...

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

What is a linear array, What is a linear array? An array is a way to re...

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Definition of algorithm, Definition of Algorithm Algorithm must have th...

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

Big o notation, This notation gives an upper bound for a function to within...

This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n))

Algorithm, what algorithms can i use for the above title in my project desi...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Infix expression into the postfix expression, Q. Write down an algorithm to...

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Boundary tag method in context of dynamic memory management, Q. How can we ...

Q. How can we free the memory by using Boundary tag method in the context of Dynamic memory management?

Rl rotation - avl tree, Example: (Double left rotation while a new node is ...

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd