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)

Array implementation of a queue, Since the stack is list of elements, the q...

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Graph traversal schemes, Various graph traversal schemes Graph Traversa...

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

In order post order, illlustraate the construction of tree of a binary tree...

illlustraate the construction of tree of a binary tree given its in order and post order transversal

Doubly linked list, How does operations like insertion, deletion occur?

How does operations like insertion, deletion occur?

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

Which sorting algorithm is adaptable to singly linked list, Which sorting a...

Which sorting algorithm is easily adaptable to singly linked lists? Simple Insertion sor t is easily adabtable to singly linked list.

What are the advantages of using assertions, Using Assertions When writ...

Using Assertions When writing code, programmer must state pre- and subtle post conditions for public operations, state class invariants and insert unreachable code assertions a

A binary tree in which levels except possibly the last, A binary tree in wh...

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

Time complexity, The  total  of  time  needed  by  an algorithm to run to i...

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Graph search using iterative deepening, Prove that uniform cost search and ...

Prove that uniform cost search and breadth- first search with constant steps are optimal when used with the Graph-Search algorithm (see Figure). Show a state space with varying ste

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