Kotlin coding test course, breadth-first search

1. Problem Description

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.

Problem

Input:
- First line: Number of vertices N (1 ≤ N ≤ 1000)
- Second line: Number of edges M (0 ≤ M ≤ 10000)
- Next M lines: Edge information (A B) - A and B represent the two connected nodes

- The last line gives the start node S and the target node T.

Output:
- Print the list of nodes in the path from S to T. If there is no path, print "PATH NOT FOUND!".

2. Problem Approach

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:

• It explores all nodes at the same depth, guaranteeing the shortest path.
• 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.

BFS Algorithm Steps

• Initialization: Mark the start node as visited and initialize distances. Insert the start node into the queue.
• Exploration Process: Repeat while the queue is not empty. Remove a node from the queue and add unvisited adjacent nodes to the queue.
• Path Tracking: Record the parent node of each node to allow for path tracking later.

3. Kotlin Code Implementation

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.

import java.util.*

data class Edge(val to: Int, val weight: Int)

fun bfs(graph: List>, start: Int, target: Int): List? {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    val parent = IntArray(graph.size) { -1 }  // Track parent nodes
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()

        // Trace back the path if the target node is found
        if (current == target) {
            return tracePath(parent, start, target)
        }

        for (edge in graph[current]) {
            if (!visited[edge.to]) {
                visited[edge.to] = true
                parent[edge.to] = current // Set parent node
                queue.add(edge.to)
            }
        }
    }
    return null // No path found
}

fun tracePath(parent: IntArray, start: Int, target: Int): List {
    val path = mutableListOf()
    var current = target

    while (current != start) {
        path.add(current)
        current = parent[current]
    }
    path.add(start)
    path.reverse()  // Reverse the list as it was added in reverse order
    return path
}

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val m = scanner.nextInt()
    val graph = List(n) { mutableListOf() }

    // Create the graph
    for (i in 0 until m) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(Edge(b, 1)) // Undirected graph, so add both ways
        graph[b].add(Edge(a, 1))
    }

    val start = scanner.nextInt() - 1
    val target = scanner.nextInt() - 1
    val result = bfs(graph, start, target)

    if (result != null) {
        println(result.joinToString(" "))
    } else {
        println("PATH NOT FOUND!")
    }
}

4. Example Input and Output

Example 1

Input:
5 4
1 2
1 3
2 4
3 5
1 5

Output:
1 3 5

Example 2

Input:
5 3
1 2
2 3
4 5
1 4

Output:
PATH NOT FOUND!

5. Conclusion

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.

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!