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

12 votes

4 answers

21

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

22

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

344 views

admin asked Dec 15, 2022

25 votes

2 answers

23

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

34 votes

4 answers

24

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

go_editor asked Sep 26, 2014

0 votes

2 answers

25

Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.

Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 BackedgeStatement II : A graph G has a cycle ...

Prince Sindhiya

269 views

Prince Sindhiya asked Aug 11, 2018

0 votes

1 answer

26

NPTEL Assignment Question
Consider the following strategy to solve the single source shortest path problem with edge weights from source s. 1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes 2. Run BFS(s) on the modified graph to ... ;s algorithm.s st This strategy will not solve the problem correctly. This strategy will only work if the graph is acyclic.

Consider the following strategy to solve the single source shortest path problem with edge weights from source s.1. Replace each edge with weight w by w edges of weight 1...

rsansiya111

1.3k views

rsansiya111 asked Dec 8, 2021

29 votes

5 answers

27

GATE CSE 2017 Set 2 | Question: 15
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNROP}$ $\text{POQNMR}$

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the ...

Madhav

8.2k views

Madhav asked Feb 14, 2017

1 votes

1 answer

28

Which of the following condition is sufficient to detect cycle in a directed graph?
Which of the following condition is sufficient to detect cycle in a directed graph? (A) There is an edge from currently being visited node to an already visited node. (B) There is an edge from currently being visited node to ... seen twice in DFS. (D) None of the bove here option B is right, but why not option A?

Which of the following condition is sufficient to detect cycle in a directed graph?(A) There is an edge from currently being visited node to an already visited node.(B) T...

Gangani_Son

13.4k views

Gangani_Son asked Dec 12, 2018

23 votes

3 answers

29

GATE IT 2008 | Question: 47
Consider the following sequence of nodes for the undirected graph given below: $a$ $b$ $e$ $f$ $d$ $g$ $c$ $a$ $b$ $e$ $f$ $c$ $g$ $d$ $a$ $d$ $g$ $e$ $b$ $c$ $f$ $a$ $d$ $b$ $c$ $g$ $e$ $f$ A Depth First Search (DFS) is started at ... first visited. Which of the above is/are possible output(s)? $1$ and $3$ only $2$ and $3$ only $2, 3$ and $4$ only $1, 2$ and $3$ only

Consider the following sequence of nodes for the undirected graph given below:$a$ $b$ $e$ $f$ $d$ $g$ $c$$a$ $b$ $e$ $f$ $c$ $g$ $d$$a$ $d$ $g$ $e$ $b$ $c$ $f$$a$ $d$ $b$...

Ishrat Jahan

8.1k views

Ishrat Jahan asked Oct 28, 2014

0 votes

1 answer

30

BFS TRAVERSAL
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?

HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?

codingo1234

386 views

codingo1234 asked Nov 21, 2018

10 votes

8 answers

31

ISRO2017-17
Which of the following data structure is useful in traversing a given graph by breadth first search? Stack Queue List None of the above

Which of the following data structure is useful in traversing a given graph by breadth first search?StackQueueListNone of the above

Arjun

13.2k views

Arjun asked May 9, 2017

6 votes

1 answer

32

Back edge,tree edge,forward edges in BFS
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed ... back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements

Consider the following statements:1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff i...

MIRIYALA JEEVAN KUMA

13.4k views

MIRIYALA JEEVAN KUMA asked Jan 27, 2018

4 votes

2 answers

33

ISRO2018-33
Which of the following is application of Breath First Search on the graph? Finding diameter of the graph Finding bipartite graph Both (a) and (b) None of the above

Which of the following is application of Breath First Search on the graph?Finding diameter of the graphFinding bipartite graphBoth (a) and (b)None of the above

Arjun

3.9k views

Arjun asked Apr 22, 2018

0 votes

1 answer

34

NIELIT 2017 July Scientist B (IT) - Section B: 5
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are 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

In a given following graph among the following sequences: abeghf abfehgabfhgeafghbe Which are depth first traversals of the above graph?I,II and IV onlyI and IV onlyII,II...

admin

921 views

admin asked Mar 30, 2020

1 votes

2 answers

35

BFS traversal path
What will be the path from A-H if BFS is used in the following graph?

What will be the path from A-H if BFS is used in the following graph?

saptarshiDey

879 views

saptarshiDey asked Feb 1, 2019

1 votes

1 answer

36

Cormen Edition 3 Exercise 22.2 Question 7 (Page No. 539)
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we ... between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.

There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may o...

KUSHAGRA गुप्ता

1.2k views

KUSHAGRA गुप्ता asked Nov 12, 2019

0 votes

1 answer

37

CLRS 22.3.1
Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK. In each cell ( , ) ij , indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color i to a vertex of color j . For each possible edge, indicate what types it can be.

Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK. In each cell ( , ) ij , indicate whether, at any point during a depth-first search of a directed gr...

sarika

1.8k views

sarika asked Aug 21, 2017

1 votes

1 answer

38

Cormen Edition 3 Exercise 22.2 Question 6 (Page No. 539)
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ ... set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.

Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$...

KUSHAGRA गुप्ता

1.7k views

KUSHAGRA गुप्ता asked Nov 12, 2019

2 votes

3 answers

39

breadth first search
The max possible height of BFS tree , if BFS is run on a complete bipartite graph Km,n where m>=1 , n>=1 with starting vertex S is

The max possible height of BFS tree , if BFS is run on a complete bipartite graph Km,n where m>=1 , n>=1 with starting vertex S is

A_i_$_h

2.7k views

A_i_$_h asked Sep 17, 2017

0 votes

1 answer

40

Cormen Edition 3 Exercise 22.2 Question 8 (Page No. 539)
The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.

The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient...

KUSHAGRA गुप्ता

1.0k views

KUSHAGRA गुप्ता asked Nov 12, 2019

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