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

Determine about the push operation, Determine about the push operation ...

Determine about the push operation A Container may or may not be accessible by keys, so it can't make assumptions about element retrieval methods (for example, it cannot have a

Types of tree ?, Binary: Each node has one, zero, or two children. This ...

Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

Define graph, A graph is a mathematical structure giving of a set of vertex...

A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Heap sort, We will start by defining a new structure called Heap. Figure 3 ...

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

Draw a b-tree., Q. Draw a B-tree of order 3 for the sequence of keys writte...

Q. Draw a B-tree of order 3 for the sequence of keys written below: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10

Draws a rectangular grid algorithms, Prepare a GUI called Hotplate GUI that...

Prepare a GUI called Hotplate GUI that holds a central panel that draws a rectangular grid that represents Element objects which should be held in a 2-dimensional array. The applic

Database design and sql queries, In assignment, you have already started th...

In assignment, you have already started the process of designing a database for the Beauty Salon mini-case (enclosed again below), mainly in the phase of conceptual database design

Random searching, write a program that find,search&replace a text string

write a program that find,search&replace a text string

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

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