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 do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func


Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

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

The number of leaf nodes in a complete binary tree of depth d is    2 d

insertion and deletion in a tree

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi