Hello, everyone! Today, we will be tackling algorithm problems for job preparation using Java. The topic this time is “Finding Cities at a Specific Distance,” utilizing graph theory and the BFS (Breadth-First Search) algorithm. We will delve deep into the fundamental concepts of algorithms and how to effectively use Java\u2019s useful data structures while solving this problem.<\/p>\n
The given cities are interconnected by roads, and each city is marked with a number. The task is to find and return all cities that can be reached by traveling a specific distance K starting from city number 1. Thus, the input consists of the number of cities N, the number of roads M, the starting city X, and the target distance K, and the output should be the city numbers sorted in ascending order.<\/p>\n
Print the numbers of the cities that can be reached at the target distance K in ascending order. If there are no reachable cities, print -1.<\/p>\n
To solve this problem, we need to construct a graph and use the BFS algorithm to find the cities reachable by the given distance K. BFS is suitable for this as it visits all vertices of the graph in level order, which helps in reaching cities at a specific distance.<\/p>\n
We use an adjacency list to represent the road relationships between cities. In Java, we can utilize To implement BFS, we use a queue to store the current city and the current distance, continuing the search until this distance reaches K. Care should be taken not to revisit cities that have already been visited during the search process. Additionally, we must compare the current distance accurately with K.<\/p>\n After collecting the cities that reached the target distance K, we sort them in ascending order and print them. If no city was reachable, we print -1.<\/p>\n The code above can be divided into three main parts. The main function initializes the graph and inputs the road information, then explores reachable cities using BFS. The BFS function uses a queue to manage the current city and distance and adds the city to the result list when it reaches the target. After all BFS explorations are completed, it sorts and outputs the reachable cities.<\/p>\n Now it’s your turn to run the code. Test with various input data to verify if the desired output is achieved. Additionally, try adding comments or modifying conditions in different parts of the code to experiment with its functionality. This will deepen your understanding of the algorithm.<\/p>\n Through this lecture, we learned the basic BFS algorithm and how to implement graphs to solve the problem of finding cities at a specific distance. As employment is the goal, I hope you solve many of these problems and build your skills. In the next lecture, we will tackle a more challenging topic. Thank you!<\/p>\nArrayList<\/code> to store adjacent cities for each city. This minimizes memory use and makes it easy to manage the relationships between cities.<\/p>\nStep 2: Implementing BFS<\/h3>\n
Step 3: Output the Results<\/h3>\n
Java Code Example<\/h2>\n
\nimport java.util.*;\n\npublic class SpecificDistanceCity {\n static ArrayListCode Explanation<\/h2>\n
Try It Yourself<\/h2>\n
Conclusion<\/h2>\n