Recent questions tagged graph-search / GATE Overflow for GATE CSE

34 votes

4 answers

31

GATE CSE 2014 Set 1 | Question: 11
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix? $\Theta(n)$ $\Theta(n+m)$ $\Theta(n^2)$ $\Theta(m^2)$

Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...

go_editor

12.2k views

go_editor asked Sep 26, 2014

24 votes

5 answers

32

GATE CSE 2003 | Question: 21
Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph? I, II and IV only I and IV only II, III and IV only I, III and IV only

Consider the following graph: Among the following sequences:abeghfabfehgabfhgeafghbeWhich are the depth-first traversals of the above graph?I, II and IV onlyI and IV only...

Kathleen

13.2k views

Kathleen asked Sep 16, 2014

38 votes

7 answers

33

GATE CSE 2001 | Question: 2.14
Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth- ... correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above

Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the short...

Kathleen

14.1k views

Kathleen asked Sep 14, 2014

25 votes

2 answers

34

GATE CSE 2000 | Question: 1.13
The most appropriate matching for the following pairs $\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\\hline \text{Y: breadth first search} & \text{2: queue} \\\hline \text{Z: sorting} & \text{3: stack} \\\hline \end{array}$ ... $\text{X - 3, Y - 2, Z - 1}$ $\text{X - 2, Y - 3, Z - 1}$

The most appropriate matching for the following pairs$$\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\\hline \text{Y: breadth first search...

Kathleen

5.5k views

Kathleen asked Sep 14, 2014

31 votes

6 answers

35

GATE CSE 2008 | Question: 19
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNPRO}$ $\text{QMNPOR}$

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:$\text{MNOPQR}$...

Kathleen

35.7k views

Kathleen asked Sep 11, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true