Question: Which of the following is not an application of breadth first search?
A Finding shortest path between two nodes
B Finding bipartiteness of a graph
C GPS navigation system
D Path Finding
Answer: Path Finding
| Application | Description | Example |
| Shortest Path | · Finding the shortest path between two nodes in an unweighted graph
· Ensuring the most efficient route |
· GPS navigation systems
· Network routing |
| Connected Components | · Identifying groups of connected nodes in an undirected graph
· Aiding in community detection |
· Social network analysis
· Network security |
| Web Crawling | · Systematically indexing web pages starting from a seed URL
· Used by search engines to build their databases. |
· Google web search · Web scraping tools |
| Social Network Analysis | · Analyzing relationships between users in social networks, including friend recommendations and network influence. | · Facebook friend suggestions
· Twitter follower analysis |
| Puzzle Solving | · Solving puzzles like the Rubik’s Cube or sliding puzzles by determining the shortest sequence of moves to reach a goal state. | · Puzzle-solving apps
· Rubik’s Cube solvers |
| Network Broadcasting | · Broadcasting information or updates to all nodes in a computer network
· Ensuring widespread communication. |
· Datacenter network management
· Message broadcasting |
| Maze Solving | · Finding the shortest path through a maze or labyrinth
· Useful in games and robotics for path planning |
· Game character navigation
· Maze-solving robots |
| Game Development | · Path finding for game characters or npcs in a virtual world
· Enabling realistic movement and interactions |
· Video games
· Virtual reality simulations |
| Recommendation Systems | · Making product or content recommendations based on user preferences and relationships in a network. | · Netflix movie recommendations
· Amazon product suggestions |
| Garbage Collection | · Identifying and collecting memory blocks that are no longer reachable or in us
· Optimizing memory management |
· Java Virtual Machine (JVM)
· Memory-efficient programming |
| Bipartite Graph Testing | · Determining if a graph can be divided into two sets with no adjacent nodes within the same set
· Useful in graph theory |
· Graph theory research
· Network flow analysis |
| Geographic Information Systems (GIS) | · Finding the shortest route between locations on a map for navigation
· Logistics and urban planning. |
· Google Maps
· Delivery route optimization |
| Natural Language Processing | · Exploring semantic networks in text data for information retrieval
· Text summarization and semantic analysis |
· Search engines
· Chatbots · Sentiment analysis |
| Routing Algorithms (Computer Networks) | · Determining optimal routes for data transmission in computer networks ensuring efficient data transfer | · Internet routing protocols (e.g., OSPF, BGP)
· Network infrastructure |
| Genealogical Research | · Tracing family trees and genealogical relationships
· Assisting in ancestry research and heritage tracking |
· Ancestry.com
· Family tree-building software |
| Robot Navigation | · Navigating robots or autonomous vehicles in unknown environments
· Avoiding obstacles and reaching destinations. |
· Self-driving cars
· Industrial automation |
| Image Processing | · Analyzing and processing pixel connectivity in images for object recognition
· Image segmentation, and more |
· Medical image analysis
· Facial recognition |