Dark Mode

Recent questions tagged graph-algorithms

0 votes

0 answers

1

TestBook TestSeries BFS Question to find 4th enqueue element
Consider the following graph. If BFS is implemented on the following graph where the root node is 1 then which of the following set of the nodes are present in the queue after performing 4th enqueue operation? 3, 4, 5 4, 6, 5 3, 4 4, 5, 6

Sahil_Lather asked in Programming Jan 28

by Sahil_Lather

79 views

1 vote

1 answer

2

Self Doubt
Does BFS and DFS traversal sequence exist for disconnected graphs? Is yes can you please give a dry run of the algorithm on a disconnected graph? According to me it should not exist as there is no edge to visit certain vertices of a different graph component from the source vertex in a disconnected graph. There is no absolute answer I could find online to this question.

Sunnidhya Roy asked in Algorithms Dec 20, 2022

by Sunnidhya Roy

154 views

1 vote

1 answer

3

Dijkstra's algorithm | Negative Weight Cycle
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUE FALSE

Souvik33 asked in Algorithms Dec 19, 2022

327 views

1 vote

1 answer

4

DRDO CSE 2022 Paper 2 | Question: 1
What is the minimum number of nodes required in a DAG (Directed Acyclic Graph) for the following block? \[ \begin{aligned} U=Z & =V+W \\ X=Y & =U+1 \\ A & =X+Y \end{aligned} \]

admin asked in Algorithms Dec 15, 2022

by admin

155 views

1 vote

0 answers

5

DRDO CSE 2022 Paper 1 | Question: 33 (a)
Consider the following graph. How many nodes (apart from $s$) does the Breadth First Search algorithm discover before discovering $t$ when starting from $s$.

admin asked in Algorithms Dec 15, 2022

by admin

66 views

0 votes

1 answer

6

mde esy test series
Which of the following statements is/are true? A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree. B. In a labelled undirected connected simple graph, G, all the breadth first search from same node form same ... is descendent of u in all possible depth-first search forest of G. (u.d is discover time of node u in DFS).

Himanshu555 asked in Algorithms Nov 8, 2022

176 views

0 votes

0 answers

7

ACE Academy Test Series q #11 || Travelling Salesman

Souvik33 asked in Algorithms Oct 31, 2022

143 views

0 votes

0 answers

8

Algorithms
How option B is incorrect.

Overflow04 asked in Algorithms Oct 20, 2022

109 views

0 votes

1 answer

9

Algorithms
Focus on the word constraint , I am little confused (in meaning of the word)here. What should be the answer 2 or 16.

Overflow04 asked in Algorithms Oct 20, 2022

91 views

0 votes

0 answers

10

CLRS
A long distance runner wants to carry only a single water bottle along the route and she can run k miles on one bottle of water. Before the race, she is given a map of all n watering stops (i.e. mile markers of these stops). Assume that the distance ... is the number of miles runner can run on a bottle of water Output: Sequence S of watering stops for the runner minimizing number of stops

LRU asked in Algorithms Oct 8, 2022

by LRU

109 views

0 votes

1 answer

11

Applied Test
Which of the following are applications for DFS when we have an unweighted directed graph at hand. 1.Single source shortest path from the source vertex. 2 Topological sorting of the vertices 3 Strongly connected components of the graph. 4 Detection of cycles in the graph. Can we use unweighted directed graph in Topological sorting ?? .

lalitver10 asked in Algorithms Sep 9, 2022

223 views

0 votes

1 answer

12

Nptel Assignment Question
Consider the following algorithm on a graph with edge weights. Sort the edges as [e1,e2,...,em] in decreasing order of cost. Start with the original graph. Consider each edge ej. If this edge is part of a cycle delete it. Which of the following is not ... at the end is a minimum cost spanning tree. Exactly m-n+1 edges will be deleted. At most n-1 edges will be deleted.

rsansiya111 asked in Algorithms Dec 8, 2021

251 views

0 votes

1 answer

13

NPTEL Assignment Question
Consider the following strategy to solve the single source shortest path problem with edge weights from source s. 1. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes 2. Run BFS(s) on the modified graph to ... 's algorithm.s st This strategy will not solve the problem correctly. This strategy will only work if the graph is acyclic.

rsansiya111 asked in Algorithms Dec 8, 2021

435 views

0 votes

2 answers

14

NPTEL Assignment Question
An undirected graph G has 300 edges. The degree of a vertex v, deg(v), is the number of edges connected to v. Suppose V = {v1,v2,...,v30}. What is the value of deg(v1)+ deg(v2) + · · · + deg(v30)? 300 600 900 None of these

rsansiya111 asked in Algorithms Dec 8, 2021

411 views

0 votes

1 answer

15

NPTEL Assignment Question
Let G be a weighted 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 not change Q: Shortest path between any pair of vertices does not change P only Q only Neither P nor Q Both P and Q

rsansiya111 asked in Algorithms Dec 7, 2021

323 views

0 votes

1 answer

16

NPTEL Assignment Question

rsansiya111 asked in Algorithms Dec 7, 2021

198 views

15 votes

5 answers

17

GATE CSE 2021 Set 2 | Question: 1
Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_1$: There exists a minimum weight edge in $G$ which is present in every minimum spanning tree of $G$. $S_2$: If every edge in $G$ has distinct weight, then $G$ has a ... are true $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false

Arjun asked in Algorithms Feb 18, 2021

by Arjun

7.8k views

11 votes

2 answers

18

GATE CSE 2021 Set 2 | Question: 46
Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$

Arjun asked in Algorithms Feb 18, 2021

by Arjun

5.3k views

11 votes

3 answers

19

GATE CSE 2021 Set 2 | Question: 55
In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{quality-score}$ of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\textsf{s}$, the quality ... $\textsf{s}$ is assumed to be $1$. The sum of the quality-scores of all vertices on the graph shown above is _______

Arjun asked in Algorithms Feb 18, 2021

by Arjun

4.2k views

5 votes

3 answers

20

GATE CSE 2021 Set 1 | Question: 17
Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is ___________.

Arjun asked in Algorithms Feb 18, 2021

by Arjun

6.9k views

Page:

1
2
3
4
5
6
...
13
next »

Recent questions tagged graph-algorithms