Question: Which of the following is not an application of depth first search?
A For generating topological sort of a graph
B For generating Strongly Connected Components of a directed graph
C Detecting cycles in the graph
D Peer to Peer Networks
Answer: Peer to Peer Networks
| Application of depth first search | Description |
| Topological Sorting | · Ordering nodes in directed acyclic graphs (dags) to represent dependencies and scheduling tasks. |
| Cycle Detection | · Identifying cycles in graphs
· Useful for deadlock detection · Dependency analysis · Plagiarism detection |
| Graph Traversal | · Traversing and searching through graphs
· Finding paths cycles and connected components. |
| Maze Solving | · Navigating through mazes and labyrinth puzzles to find a solution or determine an unsolvable path. |
| Pathfinding Algorithms | · Finding optimal paths in robotics, video games and GPS navigation by exploring potential routes. |
| Strongly Connected Components (SCC) | · Discovering SCCs in directed graphs
· Valuable in model checking · Compiler optimizations and network analysis |
| Puzzle Solving | · Solving puzzles like N-Queens
· Sudoku and the Eight-Puzzle by searching through possible states and solutions. |
| Syntax Analysis in Compilers | · Building abstract syntax trees (ASTs) from source code in compiler design for syntax analysis. |
| Web Crawling | · Indexing web pages, collecting data and following links to explore websites for web crawling and web scraping. |
| Artificial Intelligence | · Solving game trees
· Planning and state space search in AI applications like chess, robotics and decision-making. |
| Biological Research | · Applications in genome sequencing and phylogenetic tree construction
· Protein structure prediction in computational biology |
| Network Routing | · Determining efficient paths in computer networks for data packet routing and communication. |
| Natural Language Processing (NLP) | · Parsing and analyzing natural language sentences for tasks like sentence parsing and part-of-speech tagging. |