menu
search
Log In
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

Subjects

Recent questions tagged graph-algorithms

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged graph-algorithms

13 votes
3 answers
1
TIFR2011-B-35
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE? ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
asked Oct 24, 2015 in Algorithms makhdoom ghaya 1.1k views
1 vote
1 answer
2
Edge type in Undirected Graphs on Depth First Tree
Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search. Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between ... edge type between WHITE and GRAY type vertices. [ CLRS (3rd Edition) : 22-3:1; Page # 610 ]
Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search. Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between any pair of vertices during a ... Confused about the edge type between WHITE and GRAY type vertices. [ CLRS (3rd Edition) : 22-3:1; Page # 610 ]
asked Oct 22, 2015 in Algorithms Salman 295 views
5 votes
1 answer
4
dijkstra's algo
asked Oct 12, 2015 in Algorithms yes 405 views
4 votes
2 answers
5
What is the exact difference between prim's minimum spanning tree algorithm and dijkstra's single source shortest path algorithm?
I mean if we run prim's algorithm on a weighted directed graph, will it give the same shortest path? And vice-versa? Also if we run dijkstra's algorithm on a graph with negative weight cycle reachable from source, what will happen? What if we run kruskal's MST algorithm on a graph with negative weights and negative weight cycles? Thanks in advance.
asked Jun 29, 2015 in Algorithms lowOnATP 2.1k views
1 vote
2 answers
6
single source shortest path algorithm
When can we have single source shortest path algorihm runs in Big Oh of number of edges. Options are like weighted graph, undirected graph, undirected and weighted, not possilbe (i dont remember all the options)
When can we have single source shortest path algorihm runs in Big Oh of number of edges. Options are like weighted graph, undirected graph, undirected and weighted, not possilbe (i dont remember all the options)
asked Jun 26, 2015 in Algorithms Sankaranarayanan P.N 334 views
33 votes
9 answers
7
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$
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$ ... of $G$ that is not in $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 makhdoom ghaya 9k views
1 vote
2 answers
8
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.
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 Gate Aspirant 2 828 views
43 votes
5 answers
9
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$
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 always true? ... a 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 Daggerhunt 10k views
28 votes
4 answers
10
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])$
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 vertex $i$ to ... $(!A[i][j] \ \left | \right | A[j][i])$ $(A[i][j] \ \left | \right | \ !A[j][i])$
asked Nov 4, 2014 in Algorithms Ishrat Jahan 4k views
30 votes
1 answer
11
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$;
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 vertex $i$ to ... $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 Ishrat Jahan 4.8k views
19 votes
4 answers
12
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}$
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{$ ... $\text{1→ C, 2 → D, 3 → A, 4 → B}$ $\text{1→ B, 2 → A, 3 → C, 4 → D}$
asked Nov 3, 2014 in Algorithms Ishrat Jahan 2.2k views
45 votes
10 answers
13
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$
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 Ishrat Jahan 8.7k views
20 votes
3 answers
14
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)}$
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 Ishrat Jahan 5k views
22 votes
6 answers
15
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
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 $u$ ... connected 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 Ishrat Jahan 4.8k views
33 votes
6 answers
16
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 \}$
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, V \right \}, \left \{ U \right \}$ $\left \{ P, Q, S, T, V \right \}, \left \{ R \right \},\left \{ U \right \}$ $\left \{ P, Q, R, S, T, U, V \right \}$
asked Nov 1, 2014 in Algorithms Ishrat Jahan 5.8k views
34 votes
10 answers
17
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]$
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 Ishrat Jahan 6.3k views
27 votes
1 answer
18
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$
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 statements is always TRUE? Weight $(u,v) \leq 12$ Weight $(u,v) = 12$ Weight $(u,v) \geq 12$ Weight $(u,v) > 12$
asked Oct 30, 2014 in Algorithms Ishrat Jahan 5k views
18 votes
4 answers
19
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
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$. The nodes ... they 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 Ishrat Jahan 3.1k views
22 votes
4 answers
20
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 Span­ning 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)}$
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 Span­ning 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 Ishrat Jahan 6k views
19 votes
6 answers
21
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$?
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 Kathleen 3.4k views
17 votes
1 answer
22
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$
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 Kathleen 2.8k views
11 votes
1 answer
23
GATE1995-22
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).
asked Oct 8, 2014 in Algorithms Kathleen 2.2k views
23 votes
1 answer
24
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?
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 the tree; ... ; 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 Kathleen 2.4k views
27 votes
5 answers
25
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
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 tree, 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 Kathleen 4.9k views
42 votes
10 answers
26
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$
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 will be the cost of the 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 jothee 9k views
35 votes
4 answers
27
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 _________.
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 jothee 5.6k views
36 votes
6 answers
28
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.
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 every vertex 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 jothee 5.5k views
0 votes
1 answer
29
Articulation points
What will be the time complexity of an efficient algorithm which will calculate the no of 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 Akshay Jindal 360 views
68 votes
10 answers
30
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$
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 to ... There 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 Rucha Shelke 11k views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...