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

Accept a file and form a binary tree - huffman encoding, Huffman Encoding i...

Huffman Encoding is one of the very simple algorithms to compress data. Even though it is very old and simple , it is still widely used (eg : in few stages of JPEG, MPEG etc). In t

State the term access restrictions - container, What is Access Restriction...

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

Optimization Methods, Optimal solution to the problem given below. Obtain t...

Optimal solution to the problem given below. Obtain the initial solution by VAM Ware houses Stores Availibility I II III IV A 5 1 3 3 34 B 3 3 5 4 15 C 6 4 4 3 12 D 4 –1 4 2 19 Re

Depth-First Traversal, With the help of a program and a numerical example e...

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Complexity classes, Complexity classes All decision problems fall in se...

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Algorithm for determining who won rock paper scissors game, Suppose you are...

Suppose you are given the results of 5 games of rock-paper-scissors. The results are given to you on separate pieces of paper; each piece says either 'A' if the first person won, o

Multiple queue, How to create multiple queue on single array?

How to create multiple queue on single array?

Explain how the shuttle sort algorithm works, Question 1 Explain how th...

Question 1 Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps. Question 2

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

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