Depth-first search (dfs) , Data Structure & Algorithms

Assignment Help:

In this respect depth-first search (DFS) is the exact reverse process: whenever it sends a new node, it immediately continues to extend from it. It sends back to previously explored nodes only if it lay out of options. Although DFS goes to unbalanced and strange-looking exploration trees related to the orderly layers created by BFS, the combination of eager exploration with the perfect memory of a computer creates DFS very useful. It sends an algorithm template for DFS. We send special algorithms from it by specifying the subroutines traverseTreeEdge, root, init, backtrack, and traverseNonTreeEdge.

DFS creates a node when it First discovers it; started all nodes are unmarked. The main loop of DFS seems for unmarked nodes s and calls DFS(s; s) to lead a tree rooted at s. The genuine call DFS(u; v) extends all edges (v;w) out of v. The argument (u; v) display that v was reached via the edge (u; v) into v. For root nodes s, we need the .dummy. argument (s; s). We display DFS(¤; v) if the special nature of the incoming node is irrelevant for the discussion at hand. Assume now that we explore edge (v;w) within the fact DFS(¤; v). If w has been seen after, w is a node of the DFS-tree. So (v;w) is not a tree node and hence we create traverseNonTreeEdge(v;w) and prepare no recursive call of DFS. If w has not been given before, (v;w) converts a tree edge. We therefore call traverseTreeEdge(v;w), mark w and create the recursive call DFS(v;w). When we return from this call we include the next edge out of v. Once all edges out of v are included, we call backtrack on the incoming edge (u; v) to operate any summarizing or clean-up operations return and required.

 

1300_Depth First Search (DFS).png


Related Discussions:- Depth-first search (dfs)

All pairs shortest paths algorithm, In the last section, we discussed regar...

In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we

Pipelining., How branching takes place in Instruction pipeline. Explain wit...

How branching takes place in Instruction pipeline. Explain with suitable examples

The space - time trade off, The best algorithm to solve a given problem is ...

The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to

Properties of red- black tree, Any Binary search tree has to contain follow...

Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b

Determination of time complexity, Determination of Time Complexity The...

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

Representation of max-heap sequentially, Q. How do we represent a max-heap ...

Q. How do we represent a max-heap sequentially? Explain by taking a valid   example.         Ans: A max heap is also called as a descending heap, of size n is an almos

Acyclic graph, Tree is a widely used data structure employed for representi...

Tree is a widely used data structure employed for representing several problems. We studied tree like a special case of acyclic graph. Though, rooted trees are most prominent of al

Merge sort , What is the best-case number of comparisons performed by merge...

What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC                  LC Memory address       Content(LC code)

Applications of linear and binary search, The searching method are applicab...

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

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