Applied Test

Question

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 ??

 

.

Comments

2, 3, and 4 seem correct.

---

@lalitver10 For option A, we use BFS for single source shortest path.

Just to add few more points for option D:

→ If there are two back edges then it will imply that there are at least two cycles in the graph. So, one edge removal may or may not destroy all cycles and that one edge can never be back edge.

Answer 1

1. You cannot find single source shortest path using general DFS on any weighted graph. But there is some modifications which can find SSSP but it takes Quadratic complexity. (Refer: https://stackoverflow.com/a/54199609/14777974)
2. Topological sorting can be done on Directed Acyclic Graph using DFS. 
3. Strongly connected components can be find out using Kosaraju’s Algorithm which uses DFS. (Refer: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm)
4. Cycles can be detected on detection back edge using DFS.

So options (2), (3) and (4) are correct.

Comments

Hii @DebSujit @samarpita @Vishal_kumar98 ,  

They did not mentioned anything about graph is cyclic or acyclic so how topological  sorting works if the graph is may not be acyclic. 

---

@lalitver10 They told if it is possible or not. Even if the graph is cyclic you can find out using DFS that it is not possible to topologically sort that graph (i.e. finding if your graph a DAG or not).