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

Primitive data structure, Primitive Data Structure These are the basic ...

Primitive Data Structure These are the basic structure and are directly operated upon by the machine instructions. These in general have dissimilar representations on different

Insert an element after an element pointed by some pointer, Consider a link...

Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? O (1)

Tower of hanoi problem., Write an algorithm for getting solution to the Tow...

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

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

Create a binary tree , Create a class "box" that will contain a random inte...

Create a class "box" that will contain a random integer value v such that O

Flow chart, that will determine the volume of the sphere or the volume of c...

that will determine the volume of the sphere or the volume of cone or volume of pyramid depending on the choice of the user

Red black tree, red black tree construction for 4,5,6,7,8,9

red black tree construction for 4,5,6,7,8,9

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

Types of a linked list, A linked list can be of the following types:- ...

A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

Explain Hashing, What do you mean by hashing? Hashing gives the direct ...

What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func

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