Depth First Search Through Un-weighted Connected Graph , Data Structure & Algorithms

Assignment Help:

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 ;}

}

 


Related Discussions:- Depth First Search Through Un-weighted Connected Graph

Endogenous model, Question a) Describe how the endogenous model is an ...

Question a) Describe how the endogenous model is an improvement to the neo-classical model in explaining the long-run effect of investment on economic growth of a country.

Amortized algorithm analysis, In the amortized analysis, the time needed to...

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations

Write stream analogues of list processing functions, (a) Write (delay ) as...

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

Write a program for linear search, In the book the following methods are pr...

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

For loop, for (i = 0; i sequence of statements } Here, the loop e...

for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Implement an algorithm to simulate car re-organizing, Design  and implement...

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Explain threaded binary tree, Threaded Binary Tree : If a node in a bin...

Threaded Binary Tree : If a node in a binary tree is not having left or right child or it is a leaf node then that absence of child node is shown by the null pointers. The spac

SORTING ALGORIthm, the deference between insertion,selection and bubble sor...

the deference between insertion,selection and bubble sort

Union & intersection of two linklist, how to write an algorithm for unions ...

how to write an algorithm for unions & intersection of two linklists?

Implement stack using two queues, How To implement stack using two queues ,...

How To implement stack using two queues , analyze the running time of the stack operations ?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd