The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged graphalgorithms
0
votes
1
answer
1
Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edgeweighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed. Vertex Distance Parent A 0 Null B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What could be the possible value of expression x+y?
asked
Mar 10
in
Algorithms
by
noob_coder
(
141
points)

60
views
algorithms
graphalgorithms
dijkstrasalgorithm
+1
vote
1
answer
2
BFS traversal path
What will be the path from AH if BFS is used in the following graph?
asked
Feb 2
in
Algorithms
by
saptarshiDey
(
83
points)

63
views
graphalgorithms
algorithms
bfs
datastructure
0
votes
2
answers
3
made easy
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked
Jan 26
in
Algorithms
by
screddy1313
(
401
points)

53
views
graphalgorithms
dijkstrasalgorithm
programminginc
0
votes
1
answer
4
GATEBOOK2019 Mock Test127
Consider the following directed graph. Which of the following is a topological sort of the nodes of the graph? $5, 7, 10, 13, 14, 17, 20, 30$ $10, 5, 13, 14, 7, 30, 17, 20$ $10, 20, 5, 17, 13, 14, 7, 30$ $10, 5, 20, 13, 17, 30, 14, 7$
asked
Jan 19
in
Algorithms
by
GATEBOOK
Boss
(
15.3k
points)

71
views
gb2019mock1
graphalgorithms
+1
vote
0
answers
5
MadeEasy Test Series 2019: Algorithms  Graph Algorithms
Which is the best data structure to implement topological sort on directed graph? Heap Stack queue Array
asked
Jan 5
in
Algorithms
by
Nandkishor3939
Active
(
1.2k
points)

71
views
topologicalsort
madeeasytestseries
graphalgorithms
0
votes
1
answer
6
MadeEasy Test Series: Algorithms  Graph Algorithms
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS ( ... tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked
Jan 4
in
Algorithms
by
Abhishek Kumar 38
(
105
points)

71
views
madeeasytestseries
algorithms
graphsearch
graphalgorithms
0
votes
0
answers
7
Zeal Test Series 2019: Algorithms  Graph Algorithms
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?
asked
Jan 2
in
Algorithms
by
Prince Sindhiya
Loyal
(
6.2k
points)

53
views
zeal
algorithms
graphalgorithms
zeal2019
0
votes
0
answers
8
BFS and DFS  types of edges
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.
asked
Dec 30, 2018
in
Algorithms
by
Markzuck
Junior
(
633
points)

53
views
dfs
bfs
algorithms
graphalgorithms
0
votes
0
answers
9
MadeEasy Test Series: Algorithms  Graph Algorithms
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 111212 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.
asked
Dec 26, 2018
in
Algorithms
by
CHïntän ÞäTël
(
275
points)

55
views
madeeasytestseries
algorithms
graphalgorithms
0
votes
1
answer
10
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 ?
asked
Dec 25, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.3k
points)

105
views
algorithms
graphalgorithms
dfs
datastructure
bfs
+1
vote
1
answer
11
Which of the following condition is sufficient to detect cycle in a directed graph?
asked
Dec 12, 2018
in
Algorithms
by
Gangani_Son
(
163
points)

172
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
1
answer
12
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/dfsusingstack https://gateoverflow.in/161225/dfsnumberofnodesnotpushedintothestack
asked
Dec 9, 2018
in
Algorithms
by
Shivam Kasat
Active
(
1.9k
points)

55
views
dfs
algorithms
graphalgorithms
+4
votes
1
answer
13
TIFR 2019
What would be the number of distinct minimum cost spanning trees? A.32 B.64 C.16 D.8
asked
Dec 9, 2018
in
Algorithms
by
Chaitrasj
Junior
(
933
points)

441
views
tifr2019
algorithms
graphalgorithms
+1
vote
0
answers
14
Depth First Search: Finding if The graph is connected
Better Explanation??
asked
Dec 8, 2018
in
DS
by
pradeepchaudhary
Active
(
1.1k
points)

32
views
datastructure
dfs
graphalgorithms
0
votes
0
answers
15
Graph Algorithms
Dijktra Algo selects shortest path having maximum number of shortest edges, for non adjacent nodes. Is it true? Please justify..
asked
Nov 25, 2018
in
Algorithms
by
Shamim Ahmed
Active
(
2.3k
points)

44
views
algorithms
graphalgorithms
0
votes
0
answers
16
EdgeClassification 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 ... in the selected answer here. https://stackoverflow.com/questions/29631211/edgeclassificationduringbreadthfirstsearchonadirectedgraph
asked
Nov 22, 2018
in
Programming
by
Ayush Upadhyaya
Boss
(
24.9k
points)

117
views
graphalgorithms
bfs
0
votes
0
answers
17
BFS TRAVERSAL
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?
asked
Nov 21, 2018
in
Programming
by
codingo1234
Junior
(
661
points)

39
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
18
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 .
asked
Nov 21, 2018
in
Algorithms
by
eyeamgj
Loyal
(
6.7k
points)

88
views
graphalgorithms
0
votes
0
answers
19
Connected Components
asked
Nov 14, 2018
in
Graph Theory
by
Na462
Loyal
(
8.7k
points)

104
views
algorithms
graphtheory
graphalgorithms
0
votes
0
answers
20
Breadth First Search(BFS)
$01$ $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 $01$ $BFS?$ $A)$ Priority queue $B)$Stack $C)$ Doubleended queue $D)$ Linked list
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

44
views
algorithms
graphalgorithms
bfs
0
votes
0
answers
21
Graph Search
Which of the following statements are True$?$ $(1)$ In a depthfirst search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edge$.$ $(2)$ Forward and cross edges never occur in a depthfirst search of an undirected graph$.$ $(3)$ A directed graph is ... first search yields no back edges$.$ $A)1$ $B)1$ $and$ $2$ $C)2$ $and$ $3$ $D)$ $All$ $of$ $these$
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

28
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
22
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)$
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

50
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
23
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 halfopen 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
asked
Nov 10, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
29.4k
points)

60
views
algorithms
graphalgorithms
minimumspanningtrees
mst
0
votes
0
answers
24
Depth First Search
asked
Nov 7, 2018
in
Programming
by
Na462
Loyal
(
8.7k
points)

158
views
dfs
datastructure
graphalgorithms
+2
votes
1
answer
25
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?
asked
Oct 3, 2018
in
DS
by
sushmita
Boss
(
16.9k
points)

77
views
bfs
datastructure
graphalgorithms
0
votes
0
answers
26
Gate 2015
Let G(V,E) an undirected graph with positive edge weight . Dijkstra algorithm source shortest path algorithm can be implemented using binary heap data structures with time complexity ______? A. O(V^2) B. O(E+V log V) C. O((E+V) log V)
asked
Sep 17, 2018
in
Algorithms
by
karandave
(
7
points)

60
views
gate20151
algorithms
graphalgorithms
dijkstrasalgorithm
+1
vote
0
answers
27
MadeEasy Test Series: Programming & DS  Graphs
asked
Sep 17, 2018
in
DS
by
Chetan28kumar
(
181
points)

67
views
datastructure
graphalgorithms
madeeasytestseries
0
votes
0
answers
28
Strongly connected components
Consider the following graph: The number of strongly connected components of the graph are ________.
asked
Sep 15, 2018
in
Algorithms
by
syncronizing
Junior
(
945
points)

100
views
algorithms
graphalgorithms
0
votes
0
answers
29
MadeEasy Workbook: Algorithms  Graph Algorithms
Approach for Q8 and Q9 please
asked
Sep 15, 2018
in
Algorithms
by
manvi_agarwal
(
139
points)

50
views
algorithms
graphalgorithms
0
votes
0
answers
30
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.
asked
Sep 1, 2018
in
Algorithms
by
K ANKITH KUMAR
(
209
points)

76
views
dfs
algorithms
graphalgorithms
Page:
1
2
3
4
5
6
...
8
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
IIT Gandhinagar review
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
M.S admissions help
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
can anybody compare it with other new iits such...
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
One word would be "Priorities" Second word shall...
What's interesting to me is that despite having...
48,691
questions
52,776
answers
183,435
comments
68,389
users