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

0 votes

1 answer

91

BFS problem
True or False , with reason. For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic? Answer is False Explanation: FALSE. It is true that the absence of back edges with respect to a DFS tree ... a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level) Can someone explain it ?

True or False , with reason.For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic?Answer is FalseExplanation:FALSE....

Sandy Sharma

1.5k views

Sandy Sharma asked Dec 25, 2018

1 votes

1 answer

92

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

0 votes

1 answer

93

which DFS algorithm to follow?
there are multiple algorithm of DFS available and i cant figure out which one to follow for solving question asking for the nodes which aren't pushed into the stack or the nodes which are pushed more than once, Tried to figure out from ... , https://gateoverflow.in/98484/dfs-using-stack https://gateoverflow.in/161225/dfs-number-of-nodes-not-pushed-into-the-stack

there are multiple algorithm of DFS available and i cant figure out which one to follow for solving question asking for the nodes which aren’t pushed into the stack or ...

Shivam Kasat

443 views

Shivam Kasat asked Dec 9, 2018

1 votes

0 answers

94

Depth First Search: Finding if The graph is connected
Better Explanation??

Better Explanation??

pradeepchaudhary

316 views

pradeepchaudhary asked Dec 8, 2018

0 votes

0 answers

95

made easy 2019
consider a graph G given below, if the edges are having weight 1,2,3,4,5,6,7,8,9,10; then maximum possible weight a minimum weight spanning tree of G can have is according to me MST can have weight=10; what they are asking is about second minimum spanning tree; which according to me can have weight 11 i already searched but didnt find duplicate of this question !

consider a graph G given below, if the edges are having weight 1,2,3,4,5,6,7,8,9,10; then maximum possible weight a minimum weight spanning tree of G can have isaccording...

Gate Fever

503 views

Gate Fever asked Dec 2, 2018

0 votes

0 answers

96

ME- OTS 4
In worst case, for each "n" we have to check every "n then how O(n) ?

In worst case, for each "n" we have to check every "n then how O(n) ?

HeadShot

586 views

HeadShot asked Dec 1, 2018

0 votes

0 answers

97

ME - OTS 3

HeadShot

329 views

HeadShot asked Dec 1, 2018

0 votes

1 answer

98

ME OTS
Are the "n!" ways maximum possible BFS sequences ? ( Indirectly, for any given vertices is it obvious that complete graph will give max BFS sequences ? )

Are the "n!" ways maximum possible BFS sequences ? ( Indirectly, for any given vertices is it obvious that complete graph will give max BFS sequences ? )

HeadShot

280 views

HeadShot asked Nov 30, 2018

0 votes

0 answers

99

Self Doubt
Dijkstra Algo terminates and produce wrong result when graph contain negative wt Cycle What about Belman Ford??and FloydWarshall???

Dijkstra Algo terminates and produce wrong result when graph contain negative wt CycleWhat about Belman Ford??and FloydWarshall???

Abhisek Tiwari 4

189 views

Abhisek Tiwari 4 asked Nov 28, 2018

0 votes

0 answers

100

Graph Algorithms
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..

Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..

Shamim Ahmed

547 views

Shamim Ahmed asked Nov 25, 2018

0 votes

0 answers

101

IITD EET

Churchill Khangar

319 views

Churchill Khangar asked Nov 22, 2018

0 votes

0 answers

102

Edge-Classification In DIrected Graph using BFS
In BFS of a directed graph, we don't have forward edges.Only tree edge,cross edge or back edge. Below is a sample graph I have taken and classified edge types. Please verify guys whether it's correct. ... the selected answer here. https://stackoverflow.com/questions/29631211/edge-classification-during-breadth-first-search-on-a-directed-graph

In BFS of a directed graph, we don't have forward edges.Only tree edge,cross edge or back edge.Below is a sample graph I have taken and classified edge types.Please verif...

Ayush Upadhyaya

3.3k views

Ayush Upadhyaya asked Nov 22, 2018

0 votes

1 answer

103

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

383 views

codingo1234 asked Nov 21, 2018

0 votes

0 answers

104

MADE EASY TEST SERIES SELF DOUBT
In an adjacency list representation of an undirected graph G = (V,E), for any 2 sets of vertices V1 and V2 let, distance (V1,V2) be defined as the minimum of the length of shortest distance between a vertex in V1 and V2, if V1 ∩ V2 ≠ ∅, then ... computing distance (V1,V2) is : WHAT KIND OF SETS IT IS TALKING ABOUT .....?AND HOW IT CAN BE FORMED PLEASE GIVE EXAMPLE .

In an adjacency list representation of an undirected graph G = (V,E), for any 2 sets of vertices V1 and V2 let, distance (V1,V2) be defined as the minimum of the length o...

eyeamgj

767 views

eyeamgj asked Nov 21, 2018

0 votes

0 answers

105

Shortest Path

Vaishnavi01

305 views

Vaishnavi01 asked Nov 19, 2018

2 votes

0 answers

106

Connected Components

Na462

1.5k views

Na462 asked Nov 14, 2018

0 votes

0 answers

107

Breadth First Search(BFS)
$0-1$ $BFS$ (Breadth First Search)al is used to find the shortest distance between two nodes in a graph provided that the edges in the graph have the weights $0$ or $1.$Which of the following data structure is most efficient in traversing a graph by $0-1$ $BFS?$ $A)$ Priority queue $B)$Stack $C)$ Double-ended queue $D)$ Linked list

$0-1$ $BFS$ (Breadth First Search)al is used to find the shortest distance between two nodes in a graph providedthat the edges in the graph have the weights $0$ or $1.$Wh...

Lakshman Bhaiya

453 views

Lakshman Bhaiya asked Nov 13, 2018

0 votes

1 answer

108

Graph Search
Which of the following statements are true? In a depth-first search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edge Forward and cross edges never occur in a depth-first search of an undirected graph A directed graph is acyclic if and only if a depth-first search yields no back edges $1$ $1$ and $2$ $2$ and $3$ All of these

Which of the following statements are true? In a depth-first search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edgeForward and cross edg...

Lakshman Bhaiya

563 views

Lakshman Bhaiya asked Nov 13, 2018

0 votes

0 answers

109

Depth First Search (DFS)
Consider the following sequence of nodes for the undirected graph given below$:$ $(1)PQSTWVUR$ $(2)PQRSTUWV$ $(3)PQRTUSVW$ A Depth First Search (DFS) is started at node $P.$The nodes are listed in the order they are first visited. Which all of the above are possible outputs$?$ $A)Only (2)$ $B)(1) and (2)$ $C)(2) and (3)$ $D)(1) and (2)$

Consider the following sequence of nodes for the undirected graph given below$:$$(1)PQSTWVUR$$(2)PQRSTUWV$$(3)PQRTUSVW$A Depth First Search (DFS) is started at node $P.$T...

Lakshman Bhaiya

837 views

Lakshman Bhaiya asked Nov 13, 2018

1 votes

1 answer

110

Algorithm questions on graphs

I_am_winner

757 views

I_am_winner asked Nov 12, 2018

0 votes

0 answers

111

Minimum spanning tree implementation in other way
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these

Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ to construct MST so that it run...

Lakshman Bhaiya

533 views

Lakshman Bhaiya asked Nov 10, 2018

0 votes

0 answers

112

Depth First Search

Na462

1.0k views

Na462 asked Nov 7, 2018

0 votes

1 answer

113

shortest path
Can shortest path contains positive weight cycle???Please explain with examples.

Can shortest path contains positive weight cycle???Please explain with examples.

saumya mishra

278 views

saumya mishra asked Nov 6, 2018

0 votes

1 answer

114

Prim Algorithm
What is the time complexity of Prim algorithm without using min heap?

What is the time complexity of Prim algorithm without using min heap?

Alakhator

1.2k views

Alakhator asked Oct 11, 2018

2 votes

1 answer

115

general doubt on breadth first search
While doing BFS , at any time in queue suppose there are r vertices v1,v2,v3.....vr with v.d as the distance from the source. Then according to me at any time in a queue, v1.d=v2.d or v2.d=v1.d+1 But in cormen its written that v2.d<=v1.d+1 Can someone please explain?

While doing BFS , at any time in queue suppose there are r vertices v1,v2,v3.....vr with v.d as the distance from the source.Then according to me at any time in a queue,v...

sushmita

600 views

sushmita asked Oct 3, 2018

1 votes

0 answers

116

MadeEasy Test Series: Programming & DS - Graphs

Chetan28kumar

499 views

Chetan28kumar asked Sep 17, 2018

5 votes

1 answer

117

Graph
Also let me know the approach to find back edges, cross edges, forward edges, How to solve these questions

Also let me know the approach to find back edges, cross edges, forward edges,How to solve these questions

manvi_agarwal

2.5k views

manvi_agarwal asked Sep 15, 2018

0 votes

0 answers

118

Strongly connected components
Consider the following graph: The number of strongly connected components of the graph are ________.

Consider the following graph:The number of strongly connected components of the graph are ________.

syncronizing

2.5k views

syncronizing asked Sep 15, 2018

0 votes

0 answers

119

MadeEasy Workbook: Algorithms - Graph Algorithms
Approach for Q8 and Q9 please

Approach for Q8 and Q9 please

manvi_agarwal

489 views

manvi_agarwal asked Sep 15, 2018

0 votes

0 answers

120

DFS Tree
Consider the tree arcs of a DFS traversal from a source node W in an unweighted, connected, undirected, acyclic graph. The tree T formed by the tree arcs is a data structure for computing- 1. the shortest path between every pair of vertices. 2. the shortest path from W ... the graph. 3. the shortest paths from W to only those nodes that are leaves of T. 4. the longest path in the graph.

Consider the tree arcs of a DFS traversal from a source node W in an unweighted, connected, undirected, acyclic graph. The tree T formed by the tree arcs is a data struct...

K ANKITH KUMAR

696 views

K ANKITH KUMAR asked Sep 1, 2018

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