Dark Mode

Recent questions tagged graph-algorithms

1 vote

1 answer

61

MadeEasy Test Series: Algorithms - Time Complexity
#plz check??

Hradesh patel asked in Algorithms Dec 11, 2016

by Hradesh patel

738 views

3 votes

2 answers

62

shortest path
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F

dd asked in Algorithms Dec 6, 2016

by dd

2.6k views

0 votes

2 answers

63

cormen chapter 23 third edition.
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges in T. Show that T is still a minimum spanning tree for G. More formally, let T be a minimum spanning tree for G with edge weights given by weight function w. ... k, if (u, v) = (x, y). Show that T is a minimum spanning tree for G with edge weights given by w'

sushmita asked in Algorithms Dec 1, 2016

1.6k views

12 votes

4 answers

64

GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

makhdoom ghaya asked in Algorithms Nov 30, 2016

by makhdoom ghaya

2.7k views

1 vote

3 answers

65

Find shortest path

Rakesh K asked in Algorithms Nov 27, 2016

3.1k views

1 vote

0 answers

66

GATE CSE 1990 | Question: 14
The following algorithm (written in pseudo-pascal) work on an undirected graph $G$ program Explore (G) procedure Visit (u) begin if Adj (u) is not empty {comment:Adj (u) is the list of edges incident to u} then begin Select an edge from ... that each vertex can be accessed and removed from LIST in constant time. Also, show that all edges of the graph are traversed.

makhdoom ghaya asked in Algorithms Nov 25, 2016

by makhdoom ghaya

633 views

43 votes

5 answers

67

GATE CSE 2005 | Question: 82b
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges ... spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$

go_editor asked in Algorithms Nov 14, 2016

6.5k views

2 votes

1 answer

68

introduction to algorithms Thomas H.cormen q.22.2-3
In the qusetion he meant that it can be implemented using two colors by eliminating the Grey color... i think there must be one more check such that if v.pi ==nil if it must be done by two colors...only by ... this can result in insertion of same vertex twice by updating the parent and distance again which was updated initial by source vertex

Pavan Kumar Munnam asked in Algorithms Nov 14, 2016

by Pavan Kumar Munnam

1.2k views

4 votes

1 answer

69

Spanning Trees
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph $\begin{bmatrix} 0&1&1&1&0 \\ 1&0&1&1&0 \\1&1&0&0&1 \\ 1&1&0&0&1 \\0&0&1&1&0 \end{bmatrix}$

Rohan Mundhey asked in Algorithms Nov 11, 2016

by Rohan Mundhey

1.3k views

0 votes

0 answers

70

Gate 2016
Let G be aweighted connected undirected graph with distinct positive edge weights.If every edge weight is increased by the same value,then which of the following statements is/are TRUE? P: Minimum spanning tree of G does notchange Q: Shortest path between any pair of ... (D) Both PandQ answer is a. why not D ,I think Shortest path between any pair of vertices will also not change.

vishwa ratna asked in Algorithms Nov 6, 2016

by vishwa ratna

379 views

6 votes

1 answer

71

Dijkstra's algorithm
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue over a graph G = (V, E)?

vaishali jhalani asked in Algorithms Nov 5, 2016

by vaishali jhalani

3.0k views

0 votes

0 answers

72

graph
Time taken in adding/removing an edge to/from adjacent list ?

vaishali jhalani asked in Algorithms Nov 5, 2016

by vaishali jhalani

430 views

1 vote

1 answer

73

Dijkstra's Agorithm
When the graph contain negetive weight edges but no negetive weight cycle, in this case can dijkstra leads to incorrect result?

vaishali jhalani asked in Algorithms Nov 4, 2016

by vaishali jhalani

1.1k views

0 votes

1 answer

74

graph algorithm
Can we use DFS to detect the negetive weight cycle in a directed graph?

vaishali jhalani asked in Algorithms Nov 4, 2016

by vaishali jhalani

467 views

2 votes

1 answer

75

minimum spanning tree

vaishali jhalani asked in Unknown Category Nov 4, 2016

by vaishali jhalani

436 views

0 votes

0 answers

76

Kerala PSC AP Exam
Let G be a weighted undirected graph and e be an edge with mazimum weight in G. suppose there is a minimum weight spanning tree in G containing edge e. which of the following statements are always true? A) There exists a cutset in G having all edges of maximum ... G having all edges of maximum weight C) Edge e cannot be contained in a cycle D) All edges in G have the same weight

Sankaranarayanan P.N asked in DS Oct 27, 2016

by Sankaranarayanan P.N

415 views

5 votes

2 answers

77

jenny101 asked in Algorithms Oct 26, 2016

1.2k views

1 vote

1 answer

78

Shortest path length

jenny101 asked in Algorithms Oct 26, 2016

575 views

1 vote

4 answers

79

ME-ALGORITHM(BASIC LEVEL)-Q26
Consider the vertices a' and b' that are simultaneously on the function call stack at some point during the execution of DFS from vertices s' in diagraph. Which of the following must be true? S1: There exist directed path from s to a' and directed path from s to ... the above statements is/are true? a. S1 only b. S1 and S2 only c. S1 and S3 only d. S1, S2 and S3

KISHALAY DAS asked in Algorithms Oct 16, 2016

by KISHALAY DAS

1.8k views

1 vote

2 answers

80

#algo
If a directed graph G is cyclic but can be made acyclic by removing one edge,then a depth-first search in G will encounter exactly one back edge??

papesh asked in Algorithms Oct 8, 2016

by papesh

540 views

2 votes

2 answers

81

GATE Overflow | Algorithms | Test 1 | Question: 30
Match the following: i. BFS a. $O(\mid E \mid + \mid V \mid \log \mid V \mid)$ ii. DFS b. $O(E)$ iii. Kruskal's algorithm c. Stack iv. Dijikstra's Algorithm d. $O(E \log V)$ i - b, ii - c, iii - a, iv - d i - c, ii - b, iii - d, iv - a i - b, ii - c, iii - d, iv - a i - c, ii - d, iii - a, iv - b

Bikram asked in Algorithms Oct 4, 2016

by Bikram

461 views

2 votes

1 answer

82

GATE Overflow | Algorithms | Test 1 | Question: 28
Match the following i. Dijkstra's Algorithm a. All pairs shortest path ii. Bellman Ford Algorithm b. Greedy iii. Floyd-Warshall Algorithm c. Reweighting iv. Johnson Algorithm d. Single source shortest path i - c, ii - d, iii - a, iv - b i - d, ii - a, iii - c, iv - b i - b, ii - d, iii - a, iv - c i - d, ii - b, iii - a, iv - c

Bikram asked in Algorithms Oct 4, 2016

by Bikram

446 views

17 votes

1 answer

83

MadeEasy Test Series: Algorithms - Graph Algorithms
For the graph given below Dijkstra's algorithm does not provide correct shortest path tree. Suppose a new graph that is different only in weight between Q to S is created. The number of values of edge [Q to S] that ensures that Dijkstra's provide the ... tree where the values of edge (Q to S) ∈ [-20, 20] and P' is the source vertex are ______.

User007 asked in Algorithms Sep 24, 2016

2.4k views

0 votes

1 answer

84

cormen Q
Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?

gautamcse27 asked in Algorithms Sep 3, 2016

328 views

0 votes

1 answer

85

cormen Q
What is the running time of BFS if we represent its input graph by an adjacency matrix and modify the algorithm to handle this form of input?

gautamcse27 asked in Algorithms Sep 3, 2016

1.2k views

2 votes

1 answer

86

Graph traversal
Why DFS is more efficient than BFS in determining the presence of a cycle in graph ?Explain please .

annie1234 asked in Algorithms Aug 30, 2016

506 views

3 votes

2 answers

87

Self made
Which of the following can be used to find the number of connected components in a graph? A) BFS B) DFS C) Both D) None

Jithin Jayan asked in Algorithms Aug 29, 2016

by Jithin Jayan

441 views

1 vote

1 answer

88

Self made
Which Algorithm can be used to check if a graph is Bi-partated or not? A) BFS B) DFS C) Both D)None

Jithin Jayan asked in Algorithms Aug 29, 2016

by Jithin Jayan

237 views

1 vote

1 answer

89

practice questions
what is the time complexity of best algo that decides whether a given directed graph represented as adjacency matrix contains a sink or not? solve and plz explain how?

Tariq Husain Khan asked in Algorithms Aug 23, 2016

by Tariq Husain Khan

318 views

2 votes

1 answer

90

practice questions
which representation of a graph ,takes theta(V2) space and enables us to determine whether two vertices are adjacent in O(1) time? solve and plz explain how?

Tariq Husain Khan asked in Algorithms Aug 23, 2016

by Tariq Husain Khan

332 views

Page:

« prev
1
2
3
4
5
6
7
next »

Recent questions tagged graph-algorithms