Recent questions tagged graph-algorithms

+29 votes

7 answers

1

GATE2015-1-45
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

+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

+34 votes

3 answers

3

Gate2000-2.19
Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first 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

+23 votes

4 answers

4

GATE2005-IT-84b
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

+27 votes

1 answer

5

GATE2005-IT-84a
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

+16 votes

3 answers

6

GATE2005-IT-15
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}{|ll|ll|}\hline \text{1.} & \text{Bellman-Ford 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

+39 votes

9 answers

7

GATE2005-IT-14
In a depth-first 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$ $n-k-1$ $n-k$

asked Nov 3, 2014 in Algorithms by Ishrat Jahan Boss (16.3k points) | 4.7k views

+19 votes

3 answers

8

GATE2004-IT-56
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

+18 votes

4 answers

9

GATE2006-IT-47
Consider the depth-first-search 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

+29 votes

5 answers

10

GATE2006-IT-46
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

+27 votes

10 answers

11

GATE2007-IT-24
A depth-first 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

+24 votes

1 answer

12

GATE2007-IT-3, UGCNET-June2012-III-34
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

+15 votes

3 answers

13

GATE2008-IT-47
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

+17 votes

2 answers

14

GATE2008-IT-45
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

+16 votes

5 answers

15

GATE1996-17
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

+12 votes

1 answer

16

GATE1996-16
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 u-v\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

+9 votes

1 answer

17

GATE1995-22
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

+20 votes

1 answer

18

GATE1994-24
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

+22 votes

5 answers

19

GATE1994-1.22
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming Breadth-first 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. Depth-first 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

+35 votes

8 answers

20

GATE2011-54
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 i-j\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^2-n+1$ $6n-11$ $2n+1$

asked Sep 29, 2014 in Algorithms by jothee Veteran (105k points) | 5.5k views

+28 votes

2 answers

21

GATE2014-3-13
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

+30 votes

3 answers

22

GATE2014-2-14
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

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

+52 votes

9 answers

24

GATE2006-48
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

+14 votes

2 answers

25

GATE2006-47
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? $(a-b),(d-f),(b-f),(d-c),(d-e)$ $(a-b),(d-f),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(b-f),(d-e),(d-c)$

asked Sep 26, 2014 in Algorithms by Rucha Shelke Active (3.3k points) | 1.6k views

+26 votes

3 answers

26

GATE2014-1-13
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

+22 votes

3 answers

27

GATE2014-1-11
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

+38 votes

6 answers

28

GATE2012-40
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

+17 votes

2 answers

29

GATE1998-1.21, ISRO2008-16
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

+23 votes

3 answers

30

GATE2013-19
What is the time complexity of Bellman-Ford single-source 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

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 questions tagged graph-algorithms

Recent Posts

Recent Blog Comments