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
1
answer
1
Cormen Edition 3 Exercise 22.2 Question 8 (Page No. 539)
The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortestpath distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
asked
Nov 12, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4.5k
points)

93
views
cormen
graphalgorithms
bfs
descriptive
+1
vote
0
answers
2
Cormen Edition 3 Exercise 22.2 Question 7 (Page No. 539)
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we ... between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
asked
Nov 12, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4.5k
points)

46
views
cormen
graphalgorithms
bfs
descriptive
+1
vote
0
answers
3
Cormen Edition 3 Exercise 22.2 Question 6 (Page No. 539)
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ ... set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
asked
Nov 12, 2019
in
Algorithms
by
Kushagra गुप्ता
Active
(
4.5k
points)

37
views
cormen
bfs
graphalgorithms
descriptive
+2
votes
2
answers
4
UGCNETJune2019II61
Match ListI with ListII: ... (d)(ii) (a)  (ii); (b)(i); (c)(iv); (d)(iii) (a)  (iii); (b)(i); (c)(iv); (d)(ii)
asked
Jul 2, 2019
in
Algorithms
by
Arjun
Veteran
(
431k
points)

195
views
ugcnetjune2019ii
graphalgorithms
0
votes
2
answers
5
GEEKS FOR GEEKS GATE 2017 MOCK
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
asked
Jun 9, 2019
in
Algorithms
by
Hirak
Active
(
3.6k
points)

150
views
kruskalsalgorithm
graphalgorithms
greedyalgorithm
datastructures
+1
vote
1
answer
6
Difference between DAG and Multistage graph
I have trouble understanding the difference between DAG and Multistage graph. I know what each of them is But I think that a multistage graph is also a DAG. Are multistage graphs a special kind of DAG?
asked
Apr 28, 2019
in
Graph Theory
by
gmrishikumar
Active
(
2.2k
points)

91
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
7
Cormen Edition 3 Exercise 22.1 Question 8 (Page No. 593)
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected ... alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

37
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 22.1 Question 6 (Page No. 593)
Most graph algorithms that take an adjacencymatrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal link $$ a vertex with indegree $V1$ and outdegree $0$ in time $O(V)$ , given an adjacency matrix for $G$.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

33
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 22.1 Question 5 (Page No. 593)
The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ .Describe efficient algorithms for computing $G^2$ and $G$ for both the adjacency list and adjacencymatrix representations of G. Analyze the running times of your algorithms.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

17
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
1
answer
10
Cormen Edition 3 Exercise 22.1 Question 4 (Page No. 593)
Given an adjacencylist representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacencylist representation of the equivalent undirected graph $G'=(V,E')$ , where $E'$ is ... the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all selfloops removed.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

33
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
11
Cormen Edition 3 Exercise 22.1 Question 3 (Page No. 592)
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe ... algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

24
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
1
answer
12
Cormen Edition 3 Exercise 22.1 Question 2 (Page No. 592)
Give an adjacencylist representation for a complete binary tree on $7$ vertices. Give an equivalent adjacencymatrix representation. Assume that vertices are numbered from $1\ to\ 7$ as in a binary heap.
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

25
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
1
answer
13
Cormen Edition 3 Exercise 22.1 Question 1 (Page No. 592)
Given an adjacencylist representation of a directed graph, how long does it take to compute the outdegree of every vertex ? How long does it take to compute the indegrees ?
asked
Apr 7, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

23
views
cormen
algorithms
graphalgorithms
descriptive
0
votes
0
answers
14
GATE  GATECS2003
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between (A) k and n (B) k – 1 and k + 1 (C) k – 1 and n – 1 (D) k + 1 and n – k The answer is C . how is it k1?? I mean if we have only one component .?Please explain
asked
Mar 31, 2019
in
Algorithms
by
Doraemon
Junior
(
791
points)

50
views
graphalgorithms
0
votes
0
answers
15
CLRS CHAPTER 25
FOR THE EXTENDEDSHORTESTPATH if we want to find the distance between 1>4 and the 1>5 +5>4 gives the shortest path and if 1>5 gets its shortest path as 1>2>5 and 5>4 gets its shortest path as 5>3>4 then how will we get it?? as one of the operands is always from the initial array.
asked
Mar 30, 2019
in
Programming
by
Doraemon
Junior
(
791
points)

23
views
graphalgorithms
+1
vote
1
answer
16
CLRS Chapter22 Figure22.6
What are the strongly connected components in the above figure ?
asked
Mar 30, 2019
in
Algorithms
by
Doraemon
Junior
(
791
points)

72
views
stronglyconnectedcomponents
dfs
graphalgorithms
0
votes
1
answer
17
Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edgeweighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed. Vertex Distance Parent A 0 Null B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What could be the possible value of expression x+y?
asked
Mar 10, 2019
in
Algorithms
by
noob_coder
Junior
(
795
points)

338
views
algorithms
graphalgorithms
dijkstrasalgorithm
+1
vote
1
answer
18
BFS traversal path
What will be the path from AH if BFS is used in the following graph?
asked
Feb 2, 2019
in
Algorithms
by
saptarshiDey
(
117
points)

98
views
graphalgorithms
algorithms
bfs
datastructures
0
votes
2
answers
19
made easy
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked
Jan 26, 2019
in
Algorithms
by
screddy1313
(
481
points)

85
views
graphalgorithms
dijkstrasalgorithm
programminginc
+1
vote
1
answer
20
MadeEasy Test Series 2019: Algorithms  Graph Algorithms
Which is the best data structure to implement topological sort on directed graph? Heap Stack queue Array
asked
Jan 5, 2019
in
Algorithms
by
Nandkishor3939
Active
(
1.3k
points)

157
views
topologicalsort
madeeasytestseries
graphalgorithms
0
votes
2
answers
21
MadeEasy Test Series: Algorithms  Graph Algorithms
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS ( ... tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked
Jan 4, 2019
in
Algorithms
by
Abhishek Kumar 38
(
117
points)

208
views
madeeasytestseries
algorithms
graphsearch
graphalgorithms
0
votes
0
answers
22
Zeal Test Series 2019: Algorithms  Graph Algorithms
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?
asked
Jan 2, 2019
in
Algorithms
by
Prince Sindhiya
Loyal
(
5.9k
points)

77
views
zeal
algorithms
graphalgorithms
zeal2019
0
votes
0
answers
23
BFS and DFS  types of edges
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.
asked
Dec 30, 2018
in
Algorithms
by
Markzuck
Junior
(
675
points)

264
views
dfs
bfs
algorithms
graphalgorithms
+2
votes
1
answer
24
GO2019FLT147
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs with negative weight edges. ( ... P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct
asked
Dec 27, 2018
in
Algorithms
by
Ruturaj Mohanty
Active
(
2.7k
points)

186
views
go2019flt1
shortestpath
algorithms
graphalgorithms
0
votes
0
answers
25
MadeEasy Test Series: Algorithms  Graph Algorithms
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 111212 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.
asked
Dec 26, 2018
in
Algorithms
by
CHïntän ÞäTël
(
217
points)

73
views
madeeasytestseries
algorithms
graphalgorithms
0
votes
1
answer
26
BFS problem
True or False , with reason. For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic? Answer is False Explanation: FALSE. It is true that the absence of back edges with respect to a DFS tree ... a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level) Can someone explain it ?
asked
Dec 25, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

183
views
algorithms
graphalgorithms
dfs
datastructures
bfs
+1
vote
1
answer
27
Which of the following condition is sufficient to detect cycle in a directed graph?
asked
Dec 12, 2018
in
Algorithms
by
Gangani_Son
(
131
points)

414
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
1
answer
28
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
Dec 9, 2018
in
Algorithms
by
Shivam Kasat
Active
(
3.2k
points)

144
views
dfs
algorithms
graphalgorithms
+1
vote
1
answer
29
Depth First Search: Finding if The graph is connected
Better Explanation??
asked
Dec 8, 2018
in
DS
by
pradeepchaudhary
Active
(
1.2k
points)

58
views
datastructures
dfs
graphalgorithms
0
votes
0
answers
30
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, 2018
in
Algorithms
by
Shamim Ahmed
Active
(
2.5k
points)

59
views
algorithms
graphalgorithms
Page:
1
2
3
4
5
6
...
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
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,361
users