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
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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
0
answers
1
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)

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

13
views
algorithms
graphalgorithms
0
votes
0
answers
3
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
(
173
points)

51
views
dfs
algorithms
graphalgorithms
0
votes
1
answer
4
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
(
97
points)

21
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+2
votes
0
answers
5
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
(
5.7k
points)

88
views
bfs
datastructure
graphalgorithms
+1
vote
0
answers
6
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
(
5.7k
points)

25
views
dfs
datastructure
graphalgorithms
+1
vote
0
answers
7
CLRS INTRODUCTION TO ALGORITHMS 3rd Edition, CHAPTER 23 QUESTION 23.2.7
asked
Aug 19
in
Algorithms
by
aambazinga
Junior
(
969
points)

23
views
algorithms
graphalgorithms
primsalgorithm
+1
vote
1
answer
8
How Bellman ford is dynamic programming?
asked
Aug 3
in
Algorithms
by
Sandy Sharma
Junior
(
903
points)

47
views
shortestpath
algorithms
graphalgorithms
bellmanford
0
votes
0
answers
9
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.2k
points)

16
views
dfs
graphalgorithms
+1
vote
0
answers
10
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.2k
points)

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

30
views
graphtheory
graphalgorithms
0
votes
2
answers
12
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
(
231
points)

34
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
1
answer
13
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
(
163
points)

29
views
graphalgorithms
0
votes
0
answers
14
Space Complexity of Dijkastra's algorithm
asked
Jul 5
in
Algorithms
by
Hardik Maheshwari
(
59
points)

106
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
+1
vote
0
answers
15
Cormen 3rd edition chapter 22 question: 22.4.4
asked
Jul 4
in
Algorithms
by
Abhilash Mishra
(
85
points)

77
views
algorithms
graphtheory
graphalgorithms
topologicalsort
graphs
0
votes
2
answers
16
BFS Traversal
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
asked
Jun 30
in
Algorithms
by
srestha
Veteran
(
96k
points)

48
views
bfs
algorithms
graphalgorithms
0
votes
1
answer
17
graph_doubt
"edge disjoint spanning tree" means ?
asked
Jun 30
in
Algorithms
by
air1ankit
Active
(
3.7k
points)

37
views
graphalgorithms
algorithms
+1
vote
1
answer
18
#Algortihms Gate 2000 Question Self Doubt
asked
May 29
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

70
views
algorithms
graphalgorithms
usermod
usergate2005
+1
vote
1
answer
19
#Algorithms #DFS
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
asked
May 28
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

84
views
algorithms
graphalgorithms
graphtheory
dfs
0
votes
1
answer
20
#Algorithms Gate 2005 Question Self Doubt.
asked
May 23
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

106
views
algorithms
graphalgorithms
usergate2005
usermod
0
votes
0
answers
21
Gate 2003 GraphAlgorithms Question Doubt.
asked
May 18
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

60
views
usergate2003
usermod
algorithms
graphalgorithms
0
votes
2
answers
22
#Algorithm Bellman Ford uses which algorithm design technique
asked
May 17
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

90
views
algorithms
bellmanford
shortestpath
graphalgorithms
selfdoubt
0
votes
0
answers
23
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
asked
May 13
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

56
views
graphtheory
algorithms
dfs
graphalgorithms
0
votes
1
answer
24
DFS Traversal
If DFS algorithm applied starting from vertex A' which uses stack data structure then the height of stack is needed in worst case for DFS traversal is ________? Soln. Its a simple piece of cake we just need to find that path which leads to maximum nodes ... 0 and when to start counting with 1 because such type of ambiguous question always let my question go wrong and its painful :(
asked
May 6
in
Algorithms
by
Na462
Loyal
(
5.7k
points)

67
views
dfs
algorithms
graphalgorithms
0
votes
1
answer
25
Minimum Spanning Tree
1) Kruskal Algorithm 2) Prims Algorithm 3) Dijkstra Algorithm 4) Bellman Ford Algorithm 5) Floyd Warshall Algorithm Among these which one works for only i) Positive edge weight ii) Negative edge weight iii) Negative weight cycle
asked
Apr 30
in
Algorithms
by
srestha
Veteran
(
96k
points)

162
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
3
answers
26
#Algorithms #MST Doubt in MST Questions.
asked
Apr 29
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

84
views
algorithms
mst
graphalgorithms
+1
vote
1
answer
27
Self doubt
Is this statement correct?? and why? .If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail.
asked
Apr 24
in
Algorithms
by
Sandy Sharma
Junior
(
903
points)

100
views
algorithms
graphtheory
graphalgorithms
0
votes
1
answer
28
#Algorithms How is this equivalent in Kruskal's Algorithm's Time Complexity?
asked
Apr 21
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

62
views
algorithms
timecomplexity
graphalgorithms
0
votes
0
answers
29
#Algorithms How many cuts are possible are in a graph with n nodes?
asked
Apr 19
in
Algorithms
by
iarnav
Loyal
(
8.1k
points)

66
views
graphtheory
algorithms
graphalgorithms
minimumspanningtrees
0
votes
0
answers
30
Implementing Graph Data structure in C++
asked
Apr 8
in
Programming
by
Jason
Active
(
1.5k
points)

53
views
datastructure
algorithms
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
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
Digital Logic GO Classroom
Follow @csegate
Gatecse
Recent questions tagged graphalgorithms
Recent Blog Comments
@Arjun sir how to remove such post? should i hide...
[email protected]
.Plz do share @Sanjay sharma
Please post it as question
This is blog area post it as question
[email protected]
39,753
questions
46,767
answers
140,669
comments
58,539
users