The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google 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
+1
vote
1
answer
1
Which of the following condition is sufficient to detect cycle in a directed graph?
asked
2 days
ago
in
Algorithms
by
Gangani_Son
(
145
points)

29
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
1
answer
2
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
5 days
ago
in
Algorithms
by
Shivam Kasat
Junior
(
803
points)

24
views
dfs
algorithms
graphalgorithms
+3
votes
1
answer
3
TIFR 2019
What would be the number of distinct minimum cost spanning trees? A.32 B.64 C.16 D.8
asked
5 days
ago
in
Algorithms
by
Chaitrasj
Junior
(
635
points)

276
views
tifr2019
algorithms
graphalgorithms
+1
vote
0
answers
4
Depth First Search: Finding if The graph is connected
asked
6 days
ago
in
DS
by
pradeepchaudhary
Junior
(
919
points)

15
views
datastructure
dfs
graphalgorithms
0
votes
0
answers
5
Made Easy test series
Let G = (V,E) be a directed graph.Each edge of G is represented as (i,j) with length l[i,j].If there is no edge from i to j then l[i,j] = (IMAGE ATTACHED)
asked
Dec 1
in
Algorithms
by
adityaaswal
(
47
points)

43
views
madeeasytestseries
algorithms
graphalgorithms
0
votes
0
answers
6
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
in
Algorithms
by
Shamim Ahmed
Active
(
1k
points)

36
views
algorithms
graphalgorithms
0
votes
0
answers
7
EdgeClassification In DIrected Graph using BFS
asked
Nov 22
in
Programming
by
Ayush Upadhyaya
Boss
(
18.8k
points)

75
views
graphalgorithms
bfs
0
votes
0
answers
8
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
in
Programming
by
codingo1234
(
453
points)

25
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
9
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
in
Algorithms
by
eyeamgj
Loyal
(
6.3k
points)

70
views
graphalgorithms
0
votes
0
answers
10
Connected Components
asked
Nov 14
in
Graph Theory
by
Na462
Loyal
(
7.4k
points)

92
views
algorithms
graphtheory
graphalgorithms
0
votes
0
answers
11
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
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

35
views
algorithms
graphalgorithms
bfs
0
votes
0
answers
12
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
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

21
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
13
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
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

39
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
14
Minimum spanning tree implementation in other way
asked
Nov 10
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
19.5k
points)

40
views
algorithms
graphalgorithms
minimumspanningtrees
mst
0
votes
0
answers
15
Depth First Search
asked
Nov 7
in
Programming
by
Na462
Loyal
(
7.4k
points)

102
views
dfs
datastructure
graphalgorithms
+2
votes
1
answer
16
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
in
DS
by
sushmita
Boss
(
15.3k
points)

66
views
bfs
datastructure
graphalgorithms
0
votes
0
answers
17
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
in
Algorithms
by
karandave
(
7
points)

31
views
gate20151
algorithms
graphalgorithms
dijkstrasalgorithm
0
votes
0
answers
18
Strongly connected components
Consider the following graph: The number of strongly connected components of the graph are ________.
asked
Sep 15
in
Algorithms
by
syncronizing
(
499
points)

45
views
algorithms
graphalgorithms
0
votes
0
answers
19
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
in
Algorithms
by
K ANKITH KUMAR
(
191
points)

64
views
dfs
algorithms
graphalgorithms
0
votes
1
answer
20
GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
asked
Aug 31
in
Mathematical Logic
by
Nidhi Budhraja
(
203
points)

77
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+3
votes
0
answers
21
Breadth first Search
Which of following statement is true ? A. In BFS of UDG there are no back edges and forward edges. B. In BFS of Directed Graph there is no back edge and forward edges. C. In BFS of UDG for each back edge(u,v) we have 0<= v.d <= u.d D. Both b and c. Ans. A
asked
Aug 21
in
DS
by
Na462
Loyal
(
7.4k
points)

192
views
bfs
datastructure
graphalgorithms
+2
votes
0
answers
22
Depth first search
The maximum number of edges possible with UDG of n nodes,when DFS call on any random node in the graph result in stack size of 5. i.e. 5 function calls present in stack simultaneously are ......... Ans. 10
asked
Aug 21
in
DS
by
Na462
Loyal
(
7.4k
points)

59
views
dfs
datastructure
graphalgorithms
+1
vote
0
answers
23
CLRS INTRODUCTION TO ALGORITHMS 3rd Edition, CHAPTER 23 QUESTION 23.2.7
asked
Aug 19
in
Algorithms
by
aambazinga
Active
(
1.9k
points)

45
views
algorithms
graphalgorithms
primsalgorithm
+1
vote
1
answer
24
How Bellman ford is dynamic programming?
asked
Aug 3
in
Algorithms
by
Sandy Sharma
Active
(
1.1k
points)

98
views
shortestpath
algorithms
graphalgorithms
bellmanford
0
votes
0
answers
25
DFS algorithms
state TRUE or FALSE. and why Running a DFS on an undirected graph G = (V;E) always produces the same number of cross edges, no matter what order the vertex list V is in and no matter what order the adjacency lists for each vertex are in.
asked
Aug 2
in
Algorithms
by
Rishav Kumar Singh
Active
(
4.6k
points)

21
views
dfs
graphalgorithms
+1
vote
0
answers
26
shortest path algo
TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.
asked
Jul 31
in
Algorithms
by
Rishav Kumar Singh
Active
(
4.6k
points)

53
views
graphalgorithms
shortestpath
0
votes
0
answers
27
Show that T is a maximum spanning tree for G
asked
Jul 24
in
Graph Theory
by
abram19000
(
7
points)

36
views
graphtheory
graphalgorithms
0
votes
2
answers
28
Spanning Tree
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n n square matrix whose (i) diagonal elements are 0 s and (ii) nondiagonal elements are 1 s. which one of the following is TRUE? (a) Graph G has no minimum spanning tree (MST) ... n1 (c) Graph G has multiple distinct MSTs, each of cost n1 (d) Graph G has multiple spanning trees of different costs Expain?
asked
Jul 23
in
Algorithms
by
pradeepchaudhary
Junior
(
919
points)

48
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
1
answer
29
internal question of UCF
void uppercase(char *s) { int i; for (i = 0; i < strlen(s); i++) s[i] = toupper(i); } void uppercase_remix(char *s) { int i, length = strlen(s); for (i = 0; i < length; i++) s[i] = toupper(i); } void uppercase_unreliable(char ... s)  1] = rand() % 25 + 'a';} considering the above codes explain in detail the running time complexities of the 4 codes in bigoh notation?
asked
Jul 14
in
Algorithms
by
AIkiran01
(
199
points)

33
views
graphalgorithms
0
votes
2
answers
30
UGCNETJuly2018II24
Which of the following algorithms solves the singlesource shortest paths? Prim's algorithm FloysWarshall algorithm Johnson's algorithm Dijkstra's algorithm
asked
Jul 13
in
Others
by
Pooja Khatri
Active
(
5.1k
points)

164
views
ugcnetjuly2018ii
datastructure
graphalgorithms
Page:
1
2
3
4
5
6
7
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 HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged graphalgorithms
Recent Blog Comments
There is one more problem. Ppl who have...
CL013924707IN rt?
I ordered the GO BOOK 6 dec ....but still i didnt...
thankyou sir
44,240
questions
49,722
answers
163,928
comments
65,837
users