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
A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

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

Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

A full binary tree with 2n+1 nodes have n non-leaf nodes

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

red black tree construction for 4,5,6,7,8,9

1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order