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

Multiple stack in single dimensional array, Implement multiple stacks in a ...

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

Define techniques of dry running of flowcharts, Explain the term- Dry runni...

Explain the term- Dry running of flowcharts  Dry running of flowcharts is essentially a technique to: Determine output for a known set of data to check it carries out th

Abstract data type-list, It is a useful tool for indicating the logical pro...

It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

State the example of pre- and post-conditions, State the example of pre- an...

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

Memory allocation strategies, Q. Explain the various memory allocation stra...

Q. Explain the various memory allocation strategies.                                                            Ans. M e m ory Allocation Strategies are given as follow

Union & intersection of two linklist, how to write an algorithm for unions ...

how to write an algorithm for unions & intersection of two linklists?

Space-complexity of the algorithm, The space-complexity of the algorithm is...

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1). The time complexity based on the loop

An undirected graph g with n vertices and e edges, An undirected graph G wi...

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

C++ function, Write c++ function to traverse the threaded binary tree in in...

Write c++ function to traverse the threaded binary tree in inorder traversal

Algorithm, write an algorithm for the gpa of six students

write an algorithm for the gpa of six students

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