Depth First Search Through Un-weighted Connected Graph , Data Structure & Algorithms

Assignment Help:

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neither find a shortest path tree from some of the node? Why?                                                                                     

Ans:

An algorithm that does depth first search is written below:

struct node

{

int data ;

struct node *next ;

} ; int visited[MAX] ;

void dfs ( int v, struct node **p )

{

struct node *q ;

visited[v - 1] = TRUE ;

printf ( "%d\t", v ) ; q = * ( p + v - 1 ) ; while ( q != NULL )

{

if ( visited[q -> data - 1] == FALSE )

dfs ( q -> data, p ) ;

else 

q = q -> next ;}

}

 


Related Discussions:- Depth First Search Through Un-weighted Connected Graph

Write an algorithm to display this repeated calculation, The following form...

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

Frequency counts for all statements, Evaluate the frequency counts for all ...

Evaluate the frequency counts for all statements in the following given program segment. for (i=1; i ≤ n; i ++) for (j = 1; j ≤ i; j++) for (k =1; k ≤ j; k++) y ++;

Algorithm for binary search, Q. Write down the algorithm for binary search....

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

A Booth''s, Draw a flowchart of a Booth''s multiplication algorithm and exp...

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Difference between array and abstract data types, Difference between array ...

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Explain the rgb model, RGB Model The RGB model is based on the assumpti...

RGB Model The RGB model is based on the assumption that any desired shade of colour can be obtained by mixing the correct amounts of red, green, and blue light. The exact hues

Time complexity, how to learn about time complexity of a particular algorit...

how to learn about time complexity of a particular algorithm

Complexity of an algorithm, Q. Explain the complexity of an algorithm?  Wha...

Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.

Threaded Binary Tree, If a node in a binary tree is not containing left or ...

If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by

Illustrate the back face detection method, Illustrate the Back Face Detecti...

Illustrate the Back Face Detection Method A single polyhedron is a convex solid, which has no external angle between faces less  than 180° and there is a simple object space me

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