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

3 votes

0 answers

181

Ace Test series: Algorithms - Spanning Tree
Am getting 7. The answer given is 10. A - B , A - D , D - E , E - C are the edges i have included.

Am getting 7. The answer given is 10.A - B , A - D , D - E , E - C are the edges i have included.

smsubham

550 views

smsubham asked Jan 6, 2018

1 votes

2 answers

182

Dijkstra’s algorithms
Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative. Does Dijkstra’s algorithm correctly compute the shortest-path weight δ(s,t) from s to every vertex t in this graph? Justify your answer

Consider a weighted, directed acyclic graph G = (V,E,w) in which edges that leave the source vertex s may have negative weights and all other edge weights are nonnegative...

pranab ray

1.2k views

pranab ray asked Jan 3, 2018

1 votes

0 answers

183

MadeEasy Test Series: Algorithms - Spanning Tree
can someone provide a detailed solution of this??

can someone provide a detailed solution of this??

Kalpataru Bose

694 views

Kalpataru Bose asked Dec 31, 2017

1 votes

1 answer

184

madeeasy
Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles: S1 : The Bellman-Ford algorithm correctly computes shortest path lengths from a given ... The Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices. Which of the following is correct?

Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles:S1 : The Be...

garg div

371 views

garg div asked Dec 31, 2017

2 votes

0 answers

185

Minimum Spanning Tree
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible) If we divide all weights by some non zero value MST will be unchanged (answer for both positive ... ) If we add or subtract all weights by some number MST will remain unchanged. (answer for both positive and negative values)

Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible)If we divide all ...

smsubham

680 views

smsubham asked Dec 25, 2017

2 votes

1 answer

186

shortest path
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the ... We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.

Read the following statements belowFor all the below questions consider the graph as simple and has positive weight edges.(i) Let the cost of the shortest path between tw...

VIKAS TIWARI

1.0k views

VIKAS TIWARI asked Dec 13, 2017

0 votes

0 answers

187

BFS traversal sequence
Starting vertex is : $V_1$ Find the BFS traversal sequence

Starting vertex is : $V_1$Find the BFS traversal sequence

Tuhin Dutta

373 views

Tuhin Dutta asked Dec 12, 2017

11 votes

3 answers

188

TIFR CSE 2018 | Part B | Question: 13
Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associated with it. Let $T$ be the minimum weight spanning tree of $G.$ Which of the ... edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$

Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of $G$ has a distinct real weight associate...

Arjun

2.8k views

Arjun asked Dec 10, 2017

12 votes

1 answer

189

TIFR CSE 2018 | Part B | Question: 9
Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each vertex $\large v,$ let $\large \phi(v)$ be the length of the ... is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.

Let $G=(V,E)$ be a DIRECTED graph, where each edge $\large e$ has a positive weight $\large\omega(e),$ and all vertices can be reached from vertex $\large s.$ For each ve...

Arjun

2.4k views

Arjun asked Dec 10, 2017

0 votes

1 answer

190

#Graphs #DS BFS AND DFS Question?
Can BFS and DFS both work cyclic and acyclic graphs?! Kindly explain for each of 'em. Thank you!

Can BFS and DFS both work cyclic and acyclic graphs?! Kindly explain for each of 'em. Thank you!

iarnav

709 views

iarnav asked Dec 9, 2017

1 votes

1 answer

191

DFS- Depth First Search

Shubham Kumar Gupta

1.1k views

Shubham Kumar Gupta asked Dec 3, 2017

0 votes

1 answer

192

MadeEasy Workbook: Algorithms - Graph Algorithms

aaru14

577 views

aaru14 asked Dec 1, 2017

0 votes

1 answer

193

MadeEasy Subject Test: Algorithms - Graph Algorithms
complexity of kruskal algorithum for finding the minimum cost spanning tree of an undirected graph contain n vertices and m edges if the edge are already sorted.??

complexity of kruskal algorithum for finding the minimum cost spanning tree of an undirected graph contain n vertices and m edges if the edge are already sorted.??

aaru14

327 views

aaru14 asked Nov 30, 2017

0 votes

1 answer

194

Breadth first Search

VS

1.0k views

VS asked Nov 26, 2017

1 votes

1 answer

195

Algorithm:- Multistage graphs
Can someone share some multistage graph where dijkstra will fail but DP works correct?

Can someone share some multistage graph where dijkstra will fail but DP works correct?

rahul sharma 5

5.5k views

rahul sharma 5 asked Nov 18, 2017

1 votes

1 answer

196

Madeasy 2k17
Caption

Caption

kamakshi

1.4k views

kamakshi asked Nov 18, 2017

1 votes

2 answers

197

DFS , how to slove it?

Parshu gate

1.5k views

Parshu gate asked Nov 18, 2017

0 votes

1 answer

198

TestSeries
Can Bfs be applied for topological sort?

Can Bfs be applied for topological sort?

shreyansh jain

521 views

shreyansh jain asked Nov 16, 2017

1 votes

0 answers

199

doubt regarding bridge
Whether we can find a bridge in a graph with the help of different types edges like forward edge, backward edge and cross edge? Please tell logic in algorithm.

Whether we can find a bridge in a graph with the help of different types edges like forward edge, backward edge and cross edge? Please tell logic in algorithm.

Diksha Aswal

198 views

Diksha Aswal asked Nov 16, 2017

2 votes

2 answers

200

Testbook Test Series: Algorithms - Graph Algorithms
(1). Both BFS and DFS require $\Omega (N)$ storage for their operation. (2). If we double the weight of every edge in the Graph shortest path between any two vertices will not change. Which of the following is/are True ? (and in every question of shortest path we have to think about negative weight ?)

(1). Both BFS and DFS require $\Omega (N)$ storage for their operation.(2). If we double the weight of every edge in the Graph shortest path between any two vertices will...

Mr_22B

1.4k views

Mr_22B asked Nov 7, 2017

0 votes

1 answer

201

BFS TRAVERSAL

Parshu gate

449 views

Parshu gate asked Nov 5, 2017

1 votes

2 answers

202

UGC NET CSE | November 2017 | Part 2 | Question: 5
Consider the graph given below: Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are chosen is AD, AE, AG, GC, GB, BF GC, GB, BF, GA, AD, AE GC, AD, GB, GA, BF, AE AD, AG, GC, AE, GB, BF

Consider the graph given below:Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are c...

Arjun

2.4k views

Arjun asked Nov 5, 2017

0 votes

0 answers

203

Single source softest path via DFS
Hi Guys, BFS could be used for finding single source shortest path in unweighted graph. But could we use DFS also ? Please share your valuable opinion. PS: I think after little bit modification DFS could also be used but it's running time will increase.

Hi Guys,BFS could be used for finding single source shortest path in unweighted graph. But could we use DFS also ? Please share your valuable opinion.PS: I think after li...

Chhotu

312 views

Chhotu asked Nov 4, 2017

1 votes

1 answer

204

Strongly connected graph verification via BFS
Hi Guys, DFS could be used for finding directed graph is strongly connected or not. But could we use BFS also ? Please share your valuable opinion. ping @Kushagra Chatterjee, @Soumya29, @srestha, @Subarna Das and @VS ji.

Hi Guys,DFS could be used for finding directed graph is strongly connected or not. But could we use BFS also ? Please share your valuable opinion.ping @Kushagra Chatterje...

Chhotu

1.8k views

Chhotu asked Nov 4, 2017

2 votes

0 answers

205

Bellman Ford Algorithm (Edge sequence and convergence of algo.)
Hi Guys, As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, ... is your opinion ? Refer --> http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

Hi Guys,As everyone knows Bellman Ford Algorithm works on DP approach. The algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distan...

Chhotu

867 views

Chhotu asked Nov 3, 2017

3 votes

2 answers

206

MadeEasy Subject Test: Algorithms - Graph Algorithms
Consider vertices V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex s. Which of the following are always true for this digraph ? 1. There exists a directed path from s to V1 and s to ... only statement 3 is correct......How can we say that statement 1 is also correct please someone explain the reason

Consider vertices V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex s.Which of the following are always true for this digraph ...

Shivi rao

844 views

Shivi rao asked Oct 31, 2017

0 votes

1 answer

207

DFS: Practice Exercise
Q1. Consider the following DFS algorithm for cycle detection in a graph. DFS(G) for each vertex u Belongs G.V u.color = WHITE U.pi = NIL time = 0 for each vertex u Belongs G.V if u.color == WHITE DFS-VISIT(G , u) DFS-VISIT(G, u) time = ... DFS tree if we draw an edge from one leaf node to another leaf node then that edge is called cross edge. Is this statement is true ??

Q1. Consider the following DFS algorithm for cycle detection in a graph.DFS(G) for each vertex u Belongs G.V u.color = WHITE U.pi = NIL time = 0 for each vertex u Belongs...

Shubhanshu

585 views

Shubhanshu asked Oct 28, 2017

1 votes

1 answer

208

union find
Is time complexity of union find algo on an undirected graph G with V vertices and E edges O(E) ?

Is time complexity of union find algo on an undirected graph G with V vertices and E edges O(E) ?

A_i_$_h

209 views

A_i_$_h asked Oct 22, 2017

3 votes

0 answers

209

DFS: certain nodes not pushed to the stack.
Which of the following are true:- 1. DFS continues to visited first unvisited successor of each node as long as possible. 2. Certain nodes are pushed into the stack. 3. DFS first visits all the immediate successors of a node before moving to their ... nodes are pushed into the stack. 3. False -- this happens in BFS not in DFS. 4. True -- Iterative DFS.

Which of the following are true:-1. DFS continues to visited first unvisited successor of each node as long as possible.2. Certain nodes are pushed into the stack.3. DFS ...

Shubhanshu

743 views

Shubhanshu asked Oct 20, 2017

1 votes

1 answer

210

Algo:- BFS
If in a given graph all edge weights are equal and negative then BFS will correctly find out single source shortest path to all vertices,starting from vertex v? True/False?

If in a given graph all edge weights are equal and negative then BFS will correctly find out single source shortest path to all vertices,starting from vertex v? True/Fals...

rahul sharma 5

667 views

rahul sharma 5 asked Oct 4, 2017

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