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)

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Define a sparse metrics, Define a sparse metrics. A matrix in which num...

Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

Implementation of stack, Before programming a problem solution those employ...

Before programming a problem solution those employees a stack, we have to decide how to represent a stack by using the data structures which exist in our programming language. Stac

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Asymptotic analysis, Asymptotic Analysis Asymptotic analysis is dependi...

Asymptotic Analysis Asymptotic analysis is depending on the idea that as the problem size grows, the complexity can be defined as a simple proportionality to some known functio

Define null values, Define null values.  In some cases a particular ent...

Define null values.  In some cases a particular entity might not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entit

Search on a hashed file, Write a program to simulate searching over a hashe...

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Red-black tree after insertion, The above 3 cases are also considered conve...

The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le

Representation of linked list in memory, Representation of Linked list in M...

Representation of Linked list in Memory:- Each node has an info part and a pointer to the next node also known as link. The number of pointers is two in case of doubly linked

Order of the matrix, /* The program accepts matrix like input & prints the ...

/* The program accepts matrix like input & prints the 3-tuple representation of it*/ #include void main() { int a[5][5],rows,columns,i,j; printf("enter the order of

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