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
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
(
30.6k
points)

438
views
graphalgorithms
bfs
0
votes
0
answers
2
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
(
951
points)

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

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

191
views
algorithms
graphtheory
graphalgorithms
0
votes
0
answers
5
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
(
60.8k
points)

95
views
algorithms
graphalgorithms
bfs
0
votes
1
answer
6
Graph Search
Which of the following statements are true? In a depthfirst search of an undirected graph $G,$every edge of $G$ is either a tree edge or a back edge Forward and cross edges never occur in a depthfirst search of an undirected graph A directed graph is acyclic if and only if a depthfirst search yields no back edges $1$ $1$ and $2$ $2$ and $3$ All of these
asked
Nov 13, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
60.8k
points)

86
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
7
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
(
60.8k
points)

86
views
algorithms
graphalgorithms
dfs
0
votes
0
answers
8
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
(
60.8k
points)

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

195
views
dfs
datastructures
graphalgorithms
+2
votes
1
answer
10
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.8k
points)

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

88
views
datastructures
graphalgorithms
madeeasytestseries
+4
votes
1
answer
12
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
(
111
points)

457
views
algorithms
graphalgorithms
dfs
descriptive
0
votes
0
answers
13
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
(
841
points)

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

77
views
algorithms
graphalgorithms
0
votes
0
answers
15
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
(
207
points)

116
views
dfs
algorithms
graphalgorithms
0
votes
2
answers
16
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
(
205
points)

204
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+4
votes
0
answers
17
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
(
7.1k
points)

722
views
bfs
datastructures
graphalgorithms
+2
votes
0
answers
18
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
(
7.1k
points)

181
views
dfs
datastructures
graphalgorithms
+1
vote
0
answers
19
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)

157
views
algorithms
graphalgorithms
primsalgorithm
+1
vote
1
answer
20
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)

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

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

100
views
graphalgorithms
shortestpath
0
votes
0
answers
23
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)

54
views
graphtheory
graphalgorithms
0
votes
3
answers
24
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.3k
points)

95
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
1
answer
25
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)

48
views
graphalgorithms
0
votes
2
answers
26
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)

642
views
ugcnetjuly2018ii
datastructures
graphalgorithms
+1
vote
1
answer
27
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
(
101
points)

654
views
dijkstrasalgorithm
shortestpath
spacecomplexity
algorithms
graphalgorithms
greedyalgorithm
+1
vote
0
answers
28
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
(
115
points)

125
views
algorithms
graphtheory
graphalgorithms
topologicalsort
graphs
0
votes
2
answers
29
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
(
119k
points)

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

48
views
graphalgorithms
algorithms
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
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
Here is a poll on ISRO marks, you can say your...
They removed it,please create some poll or...
Did not find... post the link here
Please update your marks in gate overflow fb...
For CIL
50,834
questions
57,853
answers
199,514
comments
108,382
users