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
What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Explain about the Abstract data type Abstract data type (ADT) A set of values (the carrier set) and operations on those values

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Question

WRITE AN ALGORITHM TO READ TWO NUMBERS AND PRINT THE LOWER VALUE

Speed cameras read the time a vehicle passes a point (A) on road and then reads time it passes a second point (B) on the same road (points A and B are 100 metres apart). Speed of t

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

Chaining In this method, instead of hashing function value as location we use it as an index into an array of pointers. Every pointer access a chain that holds the element havi

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.