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 |