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
0
votes
0
answers
1
Testbook Test Series: Algorithms  Graph Algorithms
Consider the following statements: $A.$ In a weighted undirected graph $G = (V, E, w)$, breadthfirst search from a vertex s finds singlesource shortest paths from s (via parent pointers) in $O(V + E)$ time. $B.$ In a ... , then the breadthfirst search order of vertices is a valid order in which to tackle the tasks. Which of the above is TRUE?
asked
Jun 19, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

163
views
testbooktestseries
algorithms
graphalgorithms
+1
vote
1
answer
2
#Algortihms Gate 2000 Question Self Doubt
Source  Here Let G be an undirected graph. Consider a depthfirst traversal of G, and let T be the resulting depthfirst search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in ... being, since (u,v) is an edge in G therefore they can only be SIBLINGS in DFS tree and never have descendant relationship?
asked
May 29, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

126
views
algorithms
graphalgorithms
usermod
usergate2005
+3
votes
1
answer
3
#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, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

224
views
algorithms
graphalgorithms
graphtheory
dfs
+3
votes
1
answer
4
#Algorithms Gate 2005 Question Self Doubt.
Source of the question  here A sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ i $ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by ... the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.
asked
May 23, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

311
views
algorithms
graphalgorithms
usergate2005
usermod
0
votes
0
answers
5
Gate 2003 GraphAlgorithms Question Doubt.
You can refer this question here  https://gateoverflow.in/957/gate200370. I have tried so much to understand this question, but I'm not getting it, how to take the sample graph and also, how to consider the options! In fact, options are ... valid explanation at all. So, anyone help me get this in a simple layman terms, I'll be very much thankful to them.
asked
May 18, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

84
views
usergate2003
usermod
algorithms
graphalgorithms
0
votes
2
answers
6
#Algorithm Bellman Ford uses which algorithm design technique
Is it Dynamic programming?
asked
May 17, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

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

114
views
graphtheory
algorithms
dfs
graphalgorithms
0
votes
1
answer
8
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, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

178
views
dfs
algorithms
graphalgorithms
+2
votes
1
answer
9
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, 2018
in
Algorithms
by
srestha
Veteran
(
119k
points)

327
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
3
answers
10
#Algorithms #MST Doubt in MST Questions.
Question 1) The shortestpath tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
asked
Apr 29, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

156
views
algorithms
mst
graphalgorithms
+1
vote
1
answer
11
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, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

120
views
algorithms
graphtheory
graphalgorithms
+2
votes
3
answers
12
ISRO201833
Which of the following is application of Breath First Search on the graph? Finding diameter of the graph Finding bipartite graph Both (a) and (b) None of the above
asked
Apr 22, 2018
in
Algorithms
by
Arjun
Veteran
(
431k
points)

688
views
isro2018
graphalgorithms
bfs
algorithms
0
votes
1
answer
13
#Algorithms How is this equivalent in Kruskal's Algorithm's Time Complexity?
Kruskal Time complexity is O(mlogm) then how in upper bound it can be written as  O(m2) > How logm = O(m) and O (mn) > How logn = O(n)
asked
Apr 21, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

106
views
algorithms
timecomplexity
graphalgorithms
0
votes
0
answers
14
#Algorithms How many cuts are possible are in a graph with n nodes?
Some say answer is 2n and someplace else it's been told 2n11. So, what's the corrent one?
asked
Apr 19, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

95
views
graphtheory
algorithms
graphalgorithms
minimumspanningtrees
0
votes
0
answers
15
Implementing Graph Data structure in C++
//Just check create_graph function. #include <iostream> #include <malloc.h> using namespace std; struct Adj_node { int node; struct Adj_node *next; }; typedef struct Adj_node Adj_node; struct Edge { int src, dest; }; typedef struct Edge Edge; ... endl; cin>>e; create_graph(v, e); print_adj_list(); return 0; } How to get rid of this problem?
asked
Apr 8, 2018
in
Programming
by
Jason
Active
(
1.5k
points)

104
views
datastructures
algorithms
graphalgorithms
0
votes
0
answers
16
Equality of shortest path tree for given node as a root and
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the allpairs shortestpaths problem on an input adjacency matrix, we need to compute not only the shortestpath weights but also a predecessor ... isnt both things (shortestpaths tree with root $i$ and predecessor subgraph of $G$ for $i$) the same?
asked
Mar 24, 2018
in
Programming
by
GateAspirant999
Active
(
2.5k
points)

73
views
shortestpath
algorithms
graphalgorithms
0
votes
0
answers
17
DFS Modification
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
asked
Mar 21, 2018
in
Algorithms
by
ankitgupta.1729
Boss
(
17.1k
points)

266
views
dfs
algorithms
graphalgorithms
shaisimonson
+1
vote
2
answers
18
Minimum Spanning Tree Problem
asked
Mar 19, 2018
in
Algorithms
by
pankaj_vir
Boss
(
10.8k
points)

291
views
minimumspanningtrees
graphalgorithms
+1
vote
0
answers
19
Minimum Spanning Tree Problem
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then: 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
asked
Feb 19, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

248
views
minimumspanningtrees
algorithms
mst
graphalgorithms
0
votes
0
answers
20
DFSAlgorithm
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2. In such case in the graph there will be two cycles : One Cycle will contain u and other one v. There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint. Am I right?
asked
Feb 18, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

183
views
dfs
algorithms
graphalgorithms
+17
votes
6
answers
21
GATE201847
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
asked
Feb 14, 2018
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

4.9k
views
gate2018
algorithms
graphalgorithms
minimumspanningtrees
numericalanswers
+33
votes
4
answers
22
GATE201843
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label ... $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
asked
Feb 14, 2018
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

6k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
+2
votes
3
answers
23
Ace Test Series: Graph Theory  Number Of Spanning Trees
How to approach such questions ? Please provide detailed solution. Answer given is option C
asked
Feb 2, 2018
in
Graph Theory
by
kapilbk1996
(
409
points)

905
views
minimumspanningtrees
graphalgorithms
acetestseries
+6
votes
1
answer
24
Back edge,tree edge,forward edges in BFS
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed ... back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements
asked
Jan 27, 2018
in
DS
by
MIRIYALA JEEVAN KUMA
Active
(
2.4k
points)

2.2k
views
algorithms
bfs
dfs
graphalgorithms
programminginc
datastructures
+5
votes
2
answers
25
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
asked
Jan 27, 2018
in
Graph Theory
by
Balaji Jegan
Active
(
5k
points)

213
views
graphs
graphalgorithms
algorithms
+2
votes
0
answers
26
DFS depth first search
asked
Jan 25, 2018
in
DS
by
budhu
(
139
points)

121
views
datastructures
dfs
graphalgorithms
graphconnectivity
+1
vote
1
answer
27
BFS No of Teversals
How to solve these kind of questions?
asked
Jan 17, 2018
in
DS
by
Shubham Kumar Gupta
(
449
points)

164
views
bfs
algorithms
datastructures
graphalgorithms
+1
vote
0
answers
28
MadeEasy Test Series 2018: Algorithms  Graph Algorithms
Can someone work this out?
asked
Jan 16, 2018
in
Algorithms
by
Kalpataru Bose
(
413
points)

134
views
algorithms
graphalgorithms
madeeasytestseries
madeeasytestseries2018
+2
votes
1
answer
29
MadeEasy Test Series 2018: Algorithms  Graph Algorithms
Consider the following graph and sequences given below : Given answer for no of DFS traversal was 2 : S1 and S2. How S2 is a DFS traversal ?
asked
Jan 12, 2018
in
Algorithms
by
sumit chakraborty
Active
(
1.1k
points)

84
views
algorithms
graphalgorithms
madeeasytestseries2018
madeeasytestseries
+2
votes
0
answers
30
NO Of BFS traversal
what is the question asking exactly?
asked
Jan 11, 2018
in
Programming
by
gari
Active
(
3.5k
points)

161
views
bfs
algorithms
graphalgorithms
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
@Abhisheksawarn608 what makes you think...
I am getting 151 marks excluding question not...
Thank you @Arjun sir :)
Thanks for that @rohit1001
@Dumbest Kid > Jocko Podcast
50,737
questions
57,296
answers
198,262
comments
104,974
users