Depth first search, Data Structure & Algorithms

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.

Posted Date: 4/11/2013 5:06:29 AM | Location : United States







Related Discussions:- Depth first search, Assignment Help, Ask Question on Depth first search, Get Answer, Expert's Help, Depth first search Discussions

Write discussion on Depth first search
Your posts are moderated
Related Questions
Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

Hi, can you give me a quote for an E-R diagram

Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

Ask question #sdgsdgsdginimum 100 words accepted#

Painter's Algorithm As the name suggests, the algorithm follows the standard practice of a painter, who  would paint the background (such as a backdrop) first, then the major d

Explain State Space Tree If it is convenient to execute backtracking by constructing a tree of choices being made, the tree is known as a state space tree. Its root indicates a

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree.    Ans: Th

. Create a decision table that describes the movement of inventory

Your program should include three components selling, buying and managing for the use of sellers, buyers and the Manager, respectively. Provide a menu for a user to enter each comp

Best Case: If the list is sorted already then A[i] T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear. Worst Case: