Algorithm for dfs, Data Structure & Algorithms

Assignment Help:

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited.

Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if it is not already visited.

Step 3: Repeat step 2 via a new source vertex. While all adjacent vertices are visited, return to earlier source vertex and continue search from there.

If n refer to the number of vertices in the graph & the graph is represented through an adjacency matrix, then the total time taken to carry out DFS is O(n2). If G is revel by an adjacency list and the number of edges of G are e, then the time taken to carry out DFS is O(e).


Related Discussions:- Algorithm for dfs

State hsv colour model, HSV Colour Model Instead of a set of colour pri...

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

Write an algorithm to illustrate this repeated calculation, The below formu...

The below formula is used to calculate n: n = (x * x)/ (1 - x). Value x = 0 is used to stop the algorithm. Calculation is repeated using values of x until value x = 0 is input. The

ALGORITHMS, WRITE AN ALGORITHM TO READ TWO NUMBERS AND PRINT THE LOWER VALU...

WRITE AN ALGORITHM TO READ TWO NUMBERS AND PRINT THE LOWER VALUE

Sparse matrices, SPARSE MATRICES Matrices along with good number of zer...

SPARSE MATRICES Matrices along with good number of zero entries are called sparse matrices. Refer the following matrices of Figure (a)

Dijkstra's algorithm, Q. Explain Dijkstra's algorithm for finding the short...

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.  Ans: The Dijkstra's algorithm: This is a problem which is concerned with finding

Endogenous model, Question a) Describe how the endogenous model is an ...

Question a) Describe how the endogenous model is an improvement to the neo-classical model in explaining the long-run effect of investment on economic growth of a country.

Last in first out method, This method is the reverse of FIFO and assumes th...

This method is the reverse of FIFO and assumes that each issue of stock is made from latest items received in the enterprises .Thus if the last lot to be received is not sufficient

Two broad classes of collision resolution techniques, Two broad classes of ...

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Find the complexity of an algorithm, Q.1 What is an algorithm? What are the...

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

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