This problem is to find the shortest path between two nodes in a given graph. The graph is presented in the form of an adjacency list, providing the number of nodes and the information of nodes connected to each node. Your goal is to output the shortest path from a specific start node to a specific target node.<\/p>\n
\nInput:\n- First line: Number of vertices N (1 \u2264 N \u2264 1000)\n- Second line: Number of edges M (0 \u2264 M \u2264 10000)\n- Next M lines: Edge information (A B) - A and B represent the two connected nodes\n\n- The last line gives the start node S and the target node T.\n\nOutput:\n- Print the list of nodes in the path from S to T. If there is no path, print \"PATH NOT FOUND!\".\n<\/code><\/pre>\n2. Problem Approach<\/h2>\n
This problem can be solved using a typical BFS algorithm. BFS is a breadth-first search method that explores nodes close to the start node first. This allows for finding the shortest path. The main characteristics of the BFS algorithm are as follows:<\/p>\n
\n- It explores all nodes at the same depth, guaranteeing the shortest path.<\/li>\n
- Implemented using a queue, it theoretically has a time complexity of O(V + E), where V is the number of nodes and E is the number of edges.<\/li>\n<\/ul>\n
BFS Algorithm Steps<\/h3>\n\n- Initialization:<\/strong> Mark the start node as visited and initialize distances. Insert the start node into the queue.<\/li>\n
- Exploration Process:<\/strong> Repeat while the queue is not empty. Remove a node from the queue and add unvisited adjacent nodes to the queue.<\/li>\n
- Path Tracking:<\/strong> Record the parent node of each node to allow for path tracking later.<\/li>\n<\/ul>\n
3. Kotlin Code Implementation<\/h2>\n
Now, let’s implement BFS in Kotlin according to the approach above. Refer to the code below to see how to solve the given problem.<\/p>\n
\nimport java.util.*\n\ndata class Edge(val to: Int, val weight: Int)\n\nfun bfs(graph: List>, start: Int, target: Int): List? {\n val queue: Queue = LinkedList()\n val visited = BooleanArray(graph.size)\n val parent = IntArray(graph.size) { -1 } \/\/ Track parent nodes\n queue.add(start)\n visited[start] = true\n\n while (queue.isNotEmpty()) {\n val current = queue.poll()\n\n \/\/ Trace back the path if the target node is found\n if (current == target) {\n return tracePath(parent, start, target)\n }\n\n for (edge in graph[current]) {\n if (!visited[edge.to]) {\n visited[edge.to] = true\n parent[edge.to] = current \/\/ Set parent node\n queue.add(edge.to)\n }\n }\n }\n return null \/\/ No path found\n}\n\nfun tracePath(parent: IntArray, start: Int, target: Int): List {\n val path = mutableListOf()\n var current = target\n\n while (current != start) {\n path.add(current)\n current = parent[current]\n }\n path.add(start)\n path.reverse() \/\/ Reverse the list as it was added in reverse order\n return path\n}\n\nfun main() {\n val scanner = Scanner(System.`in`)\n val n = scanner.nextInt()\n val m = scanner.nextInt()\n val graph = List(n) { mutableListOf() }\n\n \/\/ Create the graph\n for (i in 0 until m) {\n val a = scanner.nextInt() - 1\n val b = scanner.nextInt() - 1\n graph[a].add(Edge(b, 1)) \/\/ Undirected graph, so add both ways\n graph[b].add(Edge(a, 1))\n }\n\n val start = scanner.nextInt() - 1\n val target = scanner.nextInt() - 1\n val result = bfs(graph, start, target)\n\n if (result != null) {\n println(result.joinToString(\" \"))\n } else {\n println(\"PATH NOT FOUND!\")\n }\n}\n<\/edge><\/int><\/int><\/int><\/int><\/list<\/code><\/pre>\n4. Example Input and Output<\/h2>\nExample 1<\/h3>\n\nInput:\n5 4\n1 2\n1 3\n2 4\n3 5\n1 5\n\nOutput:\n1 3 5\n<\/code><\/pre>\nExample 2<\/h3>\n\nInput:\n5 3\n1 2\n2 3\n4 5\n1 4\n\nOutput:\nPATH NOT FOUND!\n<\/code><\/pre>\n5. Conclusion<\/h2>\n
In this tutorial, we addressed the problem of finding the shortest path between two nodes in a graph using breadth-first search (BFS). Due to the ease of exploration provided by BFS, it is widely useful in many algorithmic problems. It is essential to develop the ability to effectively utilize BFS to solve problems in actual exams or coding tests.<\/p>\n
Now, we encourage you to tackle various problems using BFS. Enhance your understanding of algorithms through implementation in Kotlin, and develop the skills that can also be applied in real-world scenarios!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"