Register

GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 6

• edited by
255 views
0 0 votes

Which of the following is/are TRUE ?

  1. If we perform DFS on an undirected graph, there are no cross edges.
  2. If the DFS tree has no back edges, then there are no cycles in the graph.
  3. Dijkstra’s algorithm will always work correctly on any graph that has at most two negative edges.
  4. Dijkstra’s algorithm will always work correctly on any graph with negative edges but no negative cycle.

2 Answers

2 2 votes
DFS in an undirected graph can only have tree edge or back edge. Cross edge and forward edge is not possible. For the cycle to be there in the Graph, there has to be atleast 1 back edge.

Dijkstra algorithm assumes that all the edges have positive weights. If any edge has negative weight, then Dijsktra algorithm may or may not give the correct answer.
1 1 vote
i think the option B is misleading in the sense that if the DFS tree is generated, then there would never be a back edge in it.

But if the DFS traversal is going, then the presence of back edge in the graph can detect cycle, and if there is not a one, then we can say that there are no cycles in the grpah.

Therefore, they should mention that whether this is for the ongoing traversal or the DFS tree is generated.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes Test Seri...Next → · GO Classes Test Seri...
← Previous in category · GO Classes Test Seri...Next in category → · GO Classes Test Seri...
Position:
Show:

Related questions

1 1 vote
1 1 answer
238
238 views
GO Classes asked Oct 16, 2024
238 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 12
Let $\text{G = (V, E)}$ be a weighted directed graph. The shortest path from a node $s \in \text{V}$ to a node $t \in \text{V}$ will remain unchanged if: (Multiple option...
3 3 votes
3 3 answers
682
682 views
GO Classes asked Oct 16, 2024
682 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 2
Consider the given graph $\text{G}.$ Traversal trees $\text{T1}$ and $\text{T2}$ (given below) are made by DFS or BFS traversals starting from s..Which of the following i...
0 0 votes
1 1 answer
285
285 views
GO Classes asked Oct 16, 2024
285 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 13
Which of the following are CORRECT for Depth-First Search (DFS) on the graphs?Let $n$ be greater than $2$ in all options.DFS on a directed graph with $n$ vertices and $n$...
1 1 vote
1 1 answer
332
332 views
GO Classes asked Oct 16, 2024
332 views
GO Classes Test Series | Data Structures and Algorithms | Basic graph algorithms: traversals and Shortest path | Question: 7
Which of the following is correct option about $\mathrm{S} 1$ and $\mathrm{S} 2?$$\mathrm{S} 1:$ If $\text{G}$ is a weighted graph with $n$ vertices and $m$ edges that do...