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

Implementation of queue, For a queue a physical analogy is a line at bookin...

For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

Process of analysis, The objective analysis of an algorithm is to determine...

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti

What is class invariants assertion, What is Class invariants assertion ...

What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally

Insertion in list, In the array implementation of lists, elements are store...

In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

R. Studio, I need a person who has a good background in using R. Studio? I...

I need a person who has a good background in using R. Studio? In adition, a person who is good in using algorithms.

Write down any four applications of queues, Write down any four application...

Write down any four applications of queues.            Application of Queue (i)  Queue is used in time sharing system in which programs with the similar priority form a queu

Asymptotic notation.., important points on asymptotic notation to remember

important points on asymptotic notation to remember

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

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