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

Explain memory allocation strategies, Memory Allocation Strategies If i...

Memory Allocation Strategies If it is not desirable to move blocks of due storage from one area of memory to another, it must be possible to relocate memory blocks that have be

Binary search trees, In this unit, we discussed Binary Search Trees, AVL tr...

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Explain about the doubly linked list with neat diagram, Problem 1. Expl...

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

Algorithms for push and pop operation, Q. Suggest a method of implementing ...

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Difference in grounded header and circular header Link List, Q. State the d...

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c

Types of triangular matrices, Triangular Matrices Tiangular Matrices is...

Triangular Matrices Tiangular Matrices is of 2 types: a)  Lower triangular b)  Upper triangular

Efficient algorithms.., implementation of fast fourier transforms for non p...

implementation of fast fourier transforms for non power of 2

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ...

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

What is a spanning tree of a graph, What is a Spanning tree of a graph? ...

What is a Spanning tree of a graph? A Spanning Tree is any tree having of vertices of graph tree and some edges of graph is known as a spanning tree.

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