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''s queue ?

Range: A Structured Type in Ruby Ruby has a numerous structured types, comprising arrays, hashes, sets, classes, streams, and ranges. In this section we would only discuss rang

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

Comparison of Gouraud and Phong Shading Phong shading requires more calculations, but produces better results for specular reflection than Gouraud shading in the form of more r

Conceptually, the stack abstract data type mimics the information kept into a pile on a desk. Informally, first we consider a material on a desk, where we might keep separate stack

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c

Ordinary variable An ordinary variable of a easy data type can store a one element only

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h