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
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
(
885
points)

50
views
bfs
algorithms
graphalgorithms
0
votes
0
answers
2
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.2k
points)

119
views
graphalgorithms
+2
votes
0
answers
3
Connected Components
asked
Nov 14, 2018
in
Graph Theory
by
Na462
Loyal
(
6.9k
points)

162
views
algorithms
graphtheory
graphalgorithms
0
votes
0
answers
4
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
Veteran
(
55k
points)

85
views
algorithms
graphalgorithms
bfs
0
votes
0
answers
5
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
Veteran
(
55k
points)

64
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
6
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
Veteran
(
55k
points)

74
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
7
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
Veteran
(
55k
points)

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

183
views
dfs
datastructure
graphalgorithms
+2
votes
1
answer
9
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
(
17.3k
points)

99
views
bfs
datastructure
graphalgorithms
+1
vote
0
answers
10
MadeEasy Test Series: Programming & DS  Graphs
asked
Sep 17, 2018
in
DS
by
Chetan28kumar
(
143
points)

81
views
datastructure
graphalgorithms
madeeasytestseries
+3
votes
1
answer
11
Graph
Also let me know the approach to find back edges, cross edges, forward edges, How to solve these questions
asked
Sep 15, 2018
in
Algorithms
by
manvi_agarwal
(
105
points)

312
views
algorithms
graphalgorithms
dfs
descriptive
0
votes
0
answers
12
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
(
815
points)

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

68
views
algorithms
graphalgorithms
0
votes
0
answers
14
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
(
191
points)

103
views
dfs
algorithms
graphalgorithms
0
votes
1
answer
15
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, 2018
in
Mathematical Logic
by
Nidhi Budhraja
(
197
points)

169
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+4
votes
0
answers
16
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, 2018
in
DS
by
Na462
Loyal
(
6.9k
points)

620
views
bfs
datastructure
graphalgorithms
+2
votes
0
answers
17
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, 2018
in
DS
by
Na462
Loyal
(
6.9k
points)

145
views
dfs
datastructure
graphalgorithms
+1
vote
0
answers
18
CLRS INTRODUCTION TO ALGORITHMS 3rd Edition, CHAPTER 23 QUESTION 23.2.7
suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it. I know for the best case scenario when a single edge is incident from the ... up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.
asked
Aug 19, 2018
in
Algorithms
by
aambazinga
Active
(
3.4k
points)

134
views
algorithms
graphalgorithms
primsalgorithm
+1
vote
1
answer
19
How Bellman ford is dynamic programming?
What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done? BELLMANFORD(G,w,s) Code 1. INITIALIZESINGLESOURCE(G,s) 2. for i = 1 to G.V1 3. for each edge (u,v) ∈ G.E 4. RELAX(u,v,w) ... 0 RELAX(u,v,w) 1. if v.d > u.d + w(u,v) 2. v.d = u.d + w(u,v) 3. v.pi = u
asked
Aug 3, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

235
views
shortestpath
algorithms
graphalgorithms
bellmanford
0
votes
0
answers
20
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, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.6k
points)

39
views
dfs
graphalgorithms
+1
vote
0
answers
21
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, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.6k
points)

91
views
graphalgorithms
shortestpath
0
votes
0
answers
22
Show that T is a maximum spanning tree for G
Let G=(V,E) a connected graph, and p:E−>R a weight function. We denote v=n and E={e1,e2,...,em}, we suppose that ∀i p(ei)≤p(ei+1). 1Show that in a connected graph G, if T and T′ are two distinct partial ... spaninnig tree on G. 3 Give the complexity of the determination of Tm. Can some one help me in the second and third question? Thank you.
asked
Jul 24, 2018
in
Graph Theory
by
abram19000
(
5
points)

50
views
graphtheory
graphalgorithms
0
votes
2
answers
23
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, 2018
in
Algorithms
by
pradeepchaudhary
Active
(
1.2k
points)

81
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
1
answer
24
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, 2018
in
Algorithms
by
AIkiran01
(
119
points)

42
views
graphalgorithms
0
votes
2
answers
25
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, 2018
in
Others
by
Pooja Khatri
Boss
(
10.9k
points)

591
views
ugcnetjuly2018ii
datastructure
graphalgorithms
+1
vote
1
answer
26
Space Complexity of Dijkastra's algorithm
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithmspacetimecomplexity) But how ????
asked
Jul 5, 2018
in
Algorithms
by
Hardik Maheshwari
(
93
points)

593
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
+1
vote
0
answers
27
Cormen 3rd edition chapter 22 question: 22.4.4
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.
asked
Jul 4, 2018
in
Algorithms
by
Abhilash Mishra
(
107
points)

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

86
views
bfs
algorithms
graphalgorithms
0
votes
1
answer
29
graph_doubt
"edge disjoint spanning tree" means ?
asked
Jun 30, 2018
in
Algorithms
by
air1ankit
Active
(
4.5k
points)

45
views
graphalgorithms
algorithms
0
votes
0
answers
30
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)

158
views
testbooktestseries
algorithms
graphalgorithms
Page:
« prev
1
2
3
4
5
6
7
...
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
Not really. It was excluding shipping I guess....
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
50,645
questions
56,601
answers
195,854
comments
102,228
users