The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged graphalgorithms
+5
votes
0
answers
1
minimum spanning tree
asked
Jan 10, 2018
in
DS
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

113
views
minimumspanningtrees
graphalgorithms
+2
votes
0
answers
2
MadeEasy Test Series 2018: Algorithms  Graph Algorithms
For a directed graph, the absence of back edges in a DFS tree can have cycle. true or fale.please explain with an example.
asked
Jan 10, 2018
in
Algorithms
by
jaig
(
315
points)

90
views
algorithms
graphalgorithms
madeeasytestseries2018
madeeasytestseries
+1
vote
0
answers
3
MadeEasy Test Series 2018: Algorithms  Graph Algorithms
A) S1 only B) S1 and S2 only C) S1 and S3 only D) All statements are true.
asked
Jan 8, 2018
in
Algorithms
by
Abhishek Kumar Singh
Junior
(
829
points)

102
views
algorithms
graphalgorithms
madeeasytestseries2018
madeeasytestseries
+2
votes
0
answers
4
Ace Test series: Algorithms  Graph Algorithms
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Boss
(
12.5k
points)

100
views
acetestseries
minimumspanningtrees
graphalgorithms
algorithms
+2
votes
0
answers
5
Ace Test series: Algorithms  Graph Algorithms
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Boss
(
12.5k
points)

95
views
acetestseries
algorithms
graphalgorithms
+2
votes
0
answers
6
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.
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Boss
(
12.5k
points)

137
views
acetestseries
graphalgorithms
algorithms
spanningtree
minimumspanningtrees
+1
vote
2
answers
7
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 shortestpath weight δ(s,t) from s to every vertex t in this graph? Justify your answer
asked
Jan 3, 2018
in
Algorithms
by
pranab ray
Junior
(
785
points)

153
views
algorithms
dijkstrasalgorithm
graphalgorithms
+1
vote
0
answers
8
MadeEasy Test Series: Algorithms  Spanning Tree
can someone provide a detailed solution of this??
asked
Jan 1, 2018
in
Algorithms
by
Kalpataru Bose
(
423
points)

271
views
madeeasytestseries
algorithms
graphalgorithms
spanningtree
minimumspanningtrees
greedyalgorithm
+2
votes
0
answers
9
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)
asked
Dec 25, 2017
in
Algorithms
by
smsubham
Boss
(
12.5k
points)

140
views
algorithms
minimumspanningtrees
mst
graphalgorithms
0
votes
1
answer
10
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.
asked
Dec 13, 2017
in
Algorithms
by
VIKAS TIWARI
Junior
(
727
points)

219
views
algorithms
shortestpath
graphalgorithms
negativecycles
0
votes
0
answers
11
BFS traversal sequence
Starting vertex is : $V_1$ Find the BFS traversal sequence
asked
Dec 12, 2017
in
Algorithms
by
Tuhin Dutta
Boss
(
10.8k
points)

118
views
algorithms
bfs
graphalgorithms
datastructures
+4
votes
2
answers
12
TIFR2018B13
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 following statements is ... weight edge of $C$ is not in $T.$ $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$
asked
Dec 10, 2017
in
Algorithms
by
Arjun
Veteran
(
434k
points)

442
views
tifr2018
graphalgorithms
minimumspanningtrees
+7
votes
1
answer
13
TIFR2018B9
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 shortest path from $\large s$ ... If $P$ is NOT a shortest path in $G,$ then $\omega'(P)<2\times \omega(P).$ All of the above options are necessarily TRUE.
asked
Dec 10, 2017
in
Algorithms
by
Arjun
Veteran
(
434k
points)

363
views
tifr2018
graphalgorithms
shortestpath
0
votes
1
answer
14
#Graphs #DS BFS AND DFS Question?
Can BFS and DFS both work cyclic and acyclic graphs?! Kindly explain for each of 'em. Thank you!
asked
Dec 9, 2017
in
Algorithms
by
iarnav
Loyal
(
8.5k
points)

394
views
algorithms
bfs
dfs
graphalgorithms
datastructures
+1
vote
1
answer
15
DFS Depth First Search
asked
Dec 3, 2017
in
Algorithms
by
Shubham Kumar Gupta
(
449
points)

133
views
dfs
algorithms
graphalgorithms
datastructures
0
votes
1
answer
16
MadeEasy Workbook: Algorithms  Graph Algorithms
asked
Dec 1, 2017
in
Algorithms
by
aaru14
(
493
points)

132
views
algorithms
graphalgorithms
madeeasybooklet
0
votes
1
answer
17
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.??
asked
Nov 30, 2017
in
Algorithms
by
aaru14
(
493
points)

105
views
madeeasytestseries
algorithms
graphalgorithms
0
votes
1
answer
18
Breadth first Search
asked
Nov 26, 2017
in
Algorithms
by
VS
Boss
(
10.9k
points)

162
views
bfs
graphalgorithms
+1
vote
2
answers
19
DFS , how to slove it?
asked
Nov 18, 2017
in
DS
by
Parshu gate
Active
(
3.2k
points)

303
views
dfs
algorithms
graphalgorithms
datastructures
+2
votes
3
answers
20
Prims algorithm
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges in which they are added to construct Minimum Spanning Tree (MST)? PQ, PX, XV, VU, UR, RS, RW, ST PQ, PX, XV, VU, UR, RW, RS, ST PQ, QR, RW, WV, VX, VU, RS, ST PQ, QR, RW, RS, VX, VU, WV, ST
asked
Nov 17, 2017
in
Algorithms
by
Parshu gate
Active
(
3.2k
points)

542
views
algorithms
primsalgorithm
graphalgorithms
+1
vote
0
answers
21
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.
asked
Nov 16, 2017
in
Algorithms
by
Diksha Aswal
Junior
(
779
points)

38
views
graphalgorithms
+2
votes
2
answers
22
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 ?)
asked
Nov 7, 2017
in
Algorithms
by
Mr_22B
Active
(
1.2k
points)

325
views
algorithms
testbooktestseries
graphalgorithms
+2
votes
1
answer
23
Bellman Ford
A pseudo code for Bellman Ford where each edge is relaxed k times where k>=1. Let the graph G be a simple connected and undirected graph . Let number of vertices be V, and number of edges be E . int i=1; for( i=1;i<=k;i++) { For each edge (u,v) ... . (ii) For proper running of the algorithm k can be equal to V1. (iii) For proper running of the algorithm k must be equal to E.
asked
Nov 6, 2017
in
Algorithms
by
shaurya vardhan
Active
(
2.2k
points)

276
views
algorithms
bellmanford
shortestpath
graphalgorithms
negativecycles
0
votes
1
answer
24
BFS TRAVERSAL
asked
Nov 5, 2017
in
DS
by
Parshu gate
Active
(
3.2k
points)

89
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
25
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.
asked
Nov 4, 2017
in
Algorithms
by
Chhotu
Boss
(
13.8k
points)

52
views
graphalgorithms
algorithms
dfs
+1
vote
0
answers
26
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 bottomup manner. It first calculates the shortest distances which have atmost one edge in the path. Then, ... is your opinion ? Refer > http://www.geeksforgeeks.org/dynamicprogrammingset23bellmanfordalgorithm/
asked
Nov 3, 2017
in
Algorithms
by
Chhotu
Boss
(
13.8k
points)

318
views
algorithms
shortestpath
bellmanford
graphalgorithms
+3
votes
2
answers
27
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
asked
Nov 1, 2017
in
Algorithms
by
Shivi rao
Junior
(
537
points)

188
views
madeeasytestseries
algorithms
graphalgorithms
0
votes
1
answer
28
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 DFSVISIT(G , u) DFSVISIT(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 ??
asked
Oct 28, 2017
in
Algorithms
by
Shubhanshu
Boss
(
18.3k
points)

117
views
algorithms
graphalgorithms
dfs
+2
votes
0
answers
29
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.
asked
Oct 20, 2017
in
Algorithms
by
Shubhanshu
Boss
(
18.3k
points)

238
views
algorithms
dfs
graphalgorithms
datastructures
+1
vote
0
answers
30
DFS: number of nodes not pushed into the stack.
I have seen these following question: Number of Vertices pushed more than once. https://gateoverflow.in/5296/numberofvsthatarepushedmorethanonceinadfs https://gateoverflow.in/98484/dfsusingstack Vertices not pushed ... and every vertex pushed exactly once into the stack http://www.geeksforgeeks.org/depthfirsttraversalforagraph/.
asked
Oct 19, 2017
in
Programming
by
Shubhanshu
Boss
(
18.3k
points)

933
views
algorithms
graphalgorithms
dfs
datastructures
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Quick search syntax
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
Recent Posts
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
Click on the CCMT tag.
passing year 2020 is available in application...
@MiNiPanda Last yr it was 755 for non ews gen...
No, as per notification, final year not eligible....
some more experiences are there in this...
50,834
questions
57,804
answers
199,491
comments
108,253
users