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

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 ;}

}

 

Posted Date: 7/10/2012 5:24:44 AM | Location : United States







Related Discussions:- Depth First Search Through Un-weighted Connected Graph , Assignment Help, Ask Question on Depth First Search Through Un-weighted Connected Graph , Get Answer, Expert's Help, Depth First Search Through Un-weighted Connected Graph Discussions

Write discussion on Depth First Search Through Un-weighted Connected Graph
Your posts are moderated
Related Questions
Q. The two Binary Trees are said to be similar if they are both empty or if they are both non- empty and left and right sub trees are similar. Write down an algorithm to determine

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

Q. Write down an algorithm for finding a key from a sorted list using the binary search technique or method.

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

How sparse matrix stored in the memory of a computer?

Gouraud Shading The faceted appearance of a Lambert shaded model is due to each polygon having only a single colour. To avoid this effect, it is necessary to vary the colour ac

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

Searching is the procedure of looking for something: Finding one piece of data that has been stored inside a whole group of data. It is frequently the most time-consuming part of m

Q. How can we free the memory by using Boundary tag method in the context of Dynamic memory management?

1. For the ER diagram you created in assignment, the artefact of the conceptual database design, map the ER model into the relational model according to how it was designed in the