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

Sort wars - sorting algorithm, If quicksort is so quick, why bother with an...

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your mission (sho

Multikey file organization, what are the applications of multikey file orga...

what are the applications of multikey file organization?

Multidimensional array, Q. The system allocates the memory for any of the m...

Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Define strictly binary tree, Define Strictly Binary Tree Strictly Bina...

Define Strictly Binary Tree Strictly Binary Tree: - If each non leaf node in binary tree has non empty left and right sub-trees , then the tree is known as a strictly binary t

Calculation of storage complexity, Since memory is becoming more & cheaper,...

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

Random searching, write aprogram for random -search to implement if a[i]=x;...

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

Which sorting algorithms not have running time of o (n2), Which sorting al...

Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

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

Algorithm to delete node from binary search tree, Normal 0 fals...

Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Determine the effect of ruby in implementation of string, Determine the eff...

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

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