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 is hashing? what are diffrent method of hashing?

Merging two sequence using CREW merge

(1) Sort a list of distinct numbers in ascending order, using the following divide- and-conquer strategy (Quicksort): divide the list of numbers into two lists: one that contains a

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. Execute your algorithm to convert the infix expression to the post fix expression with the given infix expression as input Q = [(A + B)/(C + D) ↑ (E / F)]+ (G + H)/ I

Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements