569 views
0 votes
0 votes

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

 

.

1 Answer

3 votes
3 votes
  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.

edited by

Related questions

0 votes
0 votes
0 answers
2
Overflow04 asked Oct 20, 2022
398 views
How option B is incorrect.
0 votes
0 votes
1 answer
3
Overflow04 asked Oct 19, 2022
324 views
Focus on the word constraint , I am little confused (in meaning of the word)here. What should be the answer 2 or 16.
0 votes
0 votes
1 answer
4
gate_forum asked Jan 13, 2019
446 views
none