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
+29
votes
7
answers
1
GATE2015145
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the resultant BFS ... $T$, then which one of the following CANNOT be the value of $d(u)  d(v)$? $1$ $0$ $1$ $2$
asked
Feb 13, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

5.4k
views
gate20151
algorithms
graphalgorithms
normal
+1
vote
2
answers
2
Which of the following statement is correct regarding DFS?
Which of the following statement is correct regarding DFS? 1) All the vertices are pushed in the stack during DFS Traversal. 2) No vertex is pushed more than once in the stack during traversal.
asked
Dec 19, 2014
in
Algorithms
by
Gate Aspirant 2
(
11
points)

396
views
algorithms
graphalgorithms
dfs
+34
votes
3
answers
3
Gate20002.19
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 the traversal. Which of the following statement is ... leaf in $T$ If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$
asked
Nov 16, 2014
in
Algorithms
by
Daggerhunt
(
73
points)

5.4k
views
gate2000
algorithms
graphalgorithms
normal
+23
votes
4
answers
4
GATE2005IT84b
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge directed from ... $(!A[i][j] \ \left  \right  A[j][i])$ $(A[i][j] \ \left  \right  \ !A[j][i])$
asked
Nov 4, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

2.7k
views
gate2005it
algorithms
graphalgorithms
normal
+27
votes
1
answer
5
GATE2005IT84a
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge directed from ... $E_1:\ !A[i][j]$ and $E_2 : i = j$; $E_1 : A[i][j]$ and $E_2 : i = j + 1$;
asked
Nov 4, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

3k
views
gate2005it
algorithms
graphalgorithms
normal
+16
votes
3
answers
6
GATE2005IT15
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.$\begin{array}{llll}\hline \text{1.} & \text{BellmanFord algorithm} & \text{A:} & \text{$O( ... $\text{1→ C, 2 → D, 3 → A, 4 → B}$ $\text{1→ B, 2 → A, 3 → C, 4 → D}$
asked
Nov 3, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

1.2k
views
gate2005it
algorithms
graphalgorithms
normal
+39
votes
9
answers
7
GATE2005IT14
In a depthfirst traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is $k$ $k+1$ $nk1$ $nk$
asked
Nov 3, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

4.7k
views
gate2005it
algorithms
graphalgorithms
normal
+19
votes
3
answers
8
GATE2004IT56
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? ... $\text{(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)}$
asked
Nov 2, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

2.4k
views
gate2004it
algorithms
graphalgorithms
normal
+18
votes
4
answers
9
GATE2006IT47
Consider the depthfirstsearch of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is first visited, and finish time $f(u)$ represent the time instant when the vertex ... There are two connected components, and $Q$ and $R$ are connected There are two connected components, and $P$ and $Q$ are connected
asked
Nov 1, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

2.7k
views
gate2006it
algorithms
graphalgorithms
normal
+29
votes
5
answers
10
GATE2006IT46
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components? $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$ ... $\left \{ P, Q, R, S, T, U, V \right \}$
asked
Nov 1, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

3.4k
views
gate2006it
algorithms
graphalgorithms
normal
+27
votes
10
answers
11
GATE2007IT24
A depthfirst search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$
asked
Oct 30, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

3.7k
views
gate2007it
algorithms
graphalgorithms
normal
+24
votes
1
answer
12
GATE2007IT3, UGCNETJune2012III34
Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight 53 and the shortest path from $s$ to $v$ has weight 65. Which one of the following ... Weight $(u,v) \leq 12$ Weight $(u,v) = 12$ Weight $(u,v) \geq 12$ Weight $(u,v) > 12$
asked
Oct 30, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

3k
views
gate2007it
algorithms
graphalgorithms
normal
ugcnetjune2012iii
+15
votes
3
answers
13
GATE2008IT47
Consider the following sequence of nodes for the undirected graph given below: $a$ $b$ $e$ $f$ $d$ $g$ $c$ $a$ $b$ $e$ $f$ $c$ $g$ $d$ $a$ $d$ $g$ $e$ $b$ $c$ $f$ $a$ $d$ $b$ $c$ $g$ $e$ $f$ A Depth First Search (DFS) is started at node $a$. ... are first visited. Which of the above is/are possible output(s)? $1$ and $3$ only $2$ and $3$ only $2, 3$ and $4$ only $1, 2$ and $3$ only
asked
Oct 29, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

1.6k
views
gate2008it
algorithms
graphalgorithms
normal
+17
votes
2
answers
14
GATE2008IT45
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$
asked
Oct 29, 2014
in
Algorithms
by
Ishrat Jahan
Boss
(
16.3k
points)

2.8k
views
gate2008it
algorithms
graphalgorithms
spanningtree
normal
+16
votes
5
answers
15
GATE199617
Let $G$ be the directed, weighted graph shown in below figure We are interested in the shortest paths from $A$. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node $A$ Write down sequence of vertices in the shortest path from $A$ to $E$ What is the cost of the shortest path from $A$ to $E$?
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

2k
views
gate1996
algorithms
graphalgorithms
normal
+12
votes
1
answer
16
GATE199616
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n 1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ if the weight of the edge $(u, v)$ is $\mid uv\mid$ the weight of the edge $(u, v)$ is $u + v$
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

1.1k
views
gate1996
algorithms
graphalgorithms
spanningtree
normal
+9
votes
1
answer
17
GATE199522
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).
asked
Oct 8, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

1.3k
views
gate1995
algorithms
graphalgorithms
spanningtree
easy
+20
votes
1
answer
18
GATE199424
An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below: V: Set of all vertices in ... Output(I); Complete the algorithm by specifying the property of vertex $u$ in each case. What is the time complexity of the algorithm?
asked
Oct 6, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

1.4k
views
gate1994
algorithms
graphalgorithms
normal
+22
votes
5
answers
19
GATE19941.22
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming Breadthfirst search cannot be used to find connected components of a graph Given the prefix and postfix walks over a binary ... the binary tree cannot be uniquely constructed. Depthfirst search can be used to find connected components of a graph
asked
Oct 4, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

2.9k
views
gate1994
algorithms
normal
graphalgorithms
+35
votes
8
answers
20
GATE201154
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid ij\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. What ... minimum spanning tree (MST) of such a graph with $n$ nodes? $\frac{1}{12} (11n^2  5 n)$ $n^2n+1$ $6n11$ $2n+1$
asked
Sep 29, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

5.5k
views
gate2011
algorithms
graphalgorithms
spanningtree
normal
+28
votes
2
answers
21
GATE2014313
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
asked
Sep 28, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

3.2k
views
gate20143
algorithms
graphalgorithms
numericalanswers
normal
+30
votes
3
answers
22
GATE2014214
Consider the tree arcs of a BFS 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$ to ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
asked
Sep 28, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

2.9k
views
gate20142
algorithms
graphalgorithms
normal
0
votes
1
answer
23
Articulation points
What will be the time complexity of an efficient algorithm which will calculate the no of articulation points?
asked
Sep 27, 2014
in
Algorithms
by
Akshay Jindal
(
385
points)

290
views
algorithms
graphalgorithms
+52
votes
9
answers
24
GATE200648
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$. which one of the following statements is true? There must exist a vertex $w$ adjacent ... must exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$
asked
Sep 26, 2014
in
Algorithms
by
Rucha Shelke
Active
(
3.3k
points)

6.1k
views
gate2006
algorithms
graphalgorithms
normal
+14
votes
2
answers
25
GATE200647
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(ab),(df),(bf),(dc),(de)$ $(ab),(df),(dc),(bf),(de)$ $(df),(ab),(dc),(bf),(de)$ $(df),(ab),(bf),(de),(dc)$
asked
Sep 26, 2014
in
Algorithms
by
Rucha Shelke
Active
(
3.3k
points)

1.6k
views
gate2006
algorithms
graphalgorithms
spanningtree
normal
+26
votes
3
answers
26
GATE2014113
Consider the directed graph below given. Which one of the following is TRUE? The graph does not have any topological ordering. Both PQRS and SRQP are topological orderings. Both PSRQ and SPRQ are topological orderings. PSRQ is the only topological ordering.
asked
Sep 26, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

2.1k
views
gate20141
graphalgorithms
easy
+22
votes
3
answers
27
GATE2014111
Let $G$ be a graph with $n$ vertices and $m$ edges.What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix? $\Theta(n)$ $\Theta(n+m)$ $\Theta(n^2)$ $\Theta(m^2)$
asked
Sep 26, 2014
in
Algorithms
by
jothee
Veteran
(
105k
points)

2.5k
views
gate20141
algorithms
graphalgorithms
normal
+38
votes
6
answers
28
GATE201240
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
asked
Sep 26, 2014
in
Algorithms
by
gatecse
Boss
(
17.5k
points)

6.6k
views
gate2012
algorithms
graphalgorithms
normal
+17
votes
2
answers
29
GATE19981.21, ISRO200816
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph? Dynamic programming Backtracking Greedy Divide and Conquer
asked
Sep 26, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.2k
points)

3.5k
views
gate1998
algorithms
graphalgorithms
easy
isro2008
+23
votes
3
answers
30
GATE201319
What is the time complexity of BellmanFord singlesource shortest path algorithm on a complete graph of n vertices? $\theta(n^2)$ $\theta(n^2\log n)$ $\theta(n^3)$ $\theta(n^3\log n)$
asked
Sep 23, 2014
in
Algorithms
by
Arjun
Veteran
(
431k
points)

3.8k
views
gate2013
algorithms
graphalgorithms
normal
Page:
« prev
1
...
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
In the question associated with the register of a...
@Dumbest Kid They call in 1:8 ratio, in 2018 212...
For how many questions I can raise an objection?
https://www.isro.gov.in/sites/default/files/comput...
Can someone please post official answer key link
50,737
questions
57,306
answers
198,314
comments
105,011
users