Search results for graph-search / GATE Overflow for GATE CSE

31 votes

6 answers

1

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.8k views

Kathleen asked Sep 11, 2014

65 votes

12 answers

2

GATE IT 2005 | Question: 14
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is $k$ $k+1$ $n-k-1$ $n-k$

In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$

Ishrat Jahan

17.8k views

Ishrat Jahan asked Nov 3, 2014

51 votes

10 answers

3

GATE CSE 2015 Set 1 | Question: 45
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the ... that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from ...

makhdoom ghaya

18.3k views

makhdoom ghaya asked Feb 13, 2015

47 votes

7 answers

4

GATE CSE 2018 | Question: 30
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements.No...

gatecse

27.4k views

gatecse asked Feb 14, 2018

24 votes

5 answers

5

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

52 votes

11 answers

6

GATE IT 2007 | Question: 24
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$

A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which t...

Ishrat Jahan

13.7k views

Ishrat Jahan asked Oct 29, 2014

49 votes

8 answers

7

GATE CSE 2016 Set 2 | Question: 11
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}...

Akash Kanase

13.1k views

Akash Kanase asked Feb 12, 2016

0 votes

0 answers

8

Memory Based GATE DA 2024 | Question: 27
Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length of the shortest path from $S$ to $u$, let $(u \geqslant v)$ be an edge in ... $v$, then in the above DFS, the edge $(u, v)$ becomes: A forward edge A back edge A cross edge A tree edge

Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length...

GO Classes

196 views

GO Classes asked Feb 4

0 votes

0 answers

9

Memory Based GATE DA 2024 | Question: 34
BFS DFS question asking the number of nodes expanded BFS = DFS BFS $ DFS None

BFS DFS question asking the number of nodes expanded BFS = DFSBFS $$ DFSNone

GO Classes

142 views

GO Classes asked Feb 4

0 votes

0 answers

10

how can it have back edges?

pcla

88 views

pcla asked Jan 27

47 votes

6 answers

11

GATE CSE 2014 Set 2 | Question: 14
Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path ... graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.

Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure f...

go_editor

11.2k views

go_editor asked Sep 28, 2014

0 votes

2 answers

12

mde esy test series
Which of the following statements is/are true? A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree. B. In a labelled undirected connected simple graph, G, all the breadth first search from same node form same ... is descendent of u in all possible depth-first search forest of G. (u.d is discover time of node u in DFS).

Which of the following statements is/are true?A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree.B. In a label...

Himanshu555

626 views

Himanshu555 asked Nov 8, 2022

29 votes

8 answers

13

GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the ... are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected

Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is fi...

Ishrat Jahan

11.2k views

Ishrat Jahan asked Oct 31, 2014

43 votes

4 answers

14

GATE CSE 2014 Set 3 | Question: 13
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checkin...

go_editor

17.2k views

go_editor asked Sep 28, 2014

1 votes

2 answers

15

NIELIT 2017 July Scientist B (IT) - Section B: 4
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms? Stack for BFS and Queue for DFS Queue for BFS and Stack for DFS Stack for BFS and Stack for DFS Queue for BFS and Queue for DFS

What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms?Stack for BFS and Queue for DFSQueue f...

admin

1.4k views

admin asked Mar 30, 2020

14 votes

3 answers

16

GATE CSE 1989 | Question: 3-ixa
Which one of the following statements (s) is/are FALSE? Overlaying is used to run a program, which is longer than the address space of the computer. Optimal binary search tree construction can be performed efficiently by using dynamic programming. ... of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.

Which one of the following statements (s) is/are FALSE?Overlaying is used to run a program, which is longer than the address space of the computer.Optimal binary search t...

makhdoom ghaya

4.1k views

makhdoom ghaya asked Nov 27, 2016

38 votes

7 answers

17

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

12 votes

4 answers

18

GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

makhdoom ghaya

2.8k views

makhdoom ghaya asked Nov 30, 2016

1 votes

0 answers

19

DRDO CSE 2022 Paper 1 | Question: 33 (a)
Consider the following graph. How many nodes (apart from $s$) does the Breadth First Search algorithm discover before discovering $t$ when starting from $s$.

Consider the following graph.How many nodes (apart from $s$) does the Breadth First Search algorithm discover before discovering $t$ when starting from $s$.

admin

340 views

admin asked Dec 15, 2022

25 votes

2 answers

20

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

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