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

Sorted list using binary search technique, Write an algorithm for searching...

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Algorithms, Write an algorithm to print all even numbers in descending orde...

Write an algorithm to print all even numbers in descending order and draw the flowchart

Problem logicall, Given a list containing Province, CustomerName and SalesV...

Given a list containing Province, CustomerName and SalesValue (sorted by Province and CustomerName), describe an algorithm you could use that would output each CustomerName and Sal

Explain divide and conquer algorithms, Explain divide and conquer algorithm...

Explain divide and conquer algorithms  Divide  and  conquer  is  probably  the  best  known  general  algorithm  design  method.  It   work according to the following general p

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P...

5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Develop a material requirements plan, The below figure illustrates the BOM ...

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Graph connectivity, A connected graph is a graph wherein path exists among ...

A connected graph is a graph wherein path exists among every pair of vertices. A strongly connected graph is a directed graph wherein every pair of distinct vertices is connecte

The complexity of multiplying two matrices, The complexity of multiplying t...

The complexity of multiplying two matrices of order m*n and n*p is    mnp

Infix expression into the postfix expression, Q. Convert the given infix ex...

Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix

Discuss the brute force algorithm, Question 1 What do you mean by Amortiza...

Question 1 What do you mean by Amortization? Question 2 Explain the following Big Oh notation (O) Omega notation (Ω) Theta notation (Θ)   Question 3 Di

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