Introduction

This tutorial is part of a collection tutorials on basic data structures and algorithms that are created using Kotlin. This project is useful if you are trying to get more fluency in Kotlin or need a refresher to do interview prep for software engineering roles.

How to run this project

You can get the code for this and all the other tutorials in this collection from this github repo. Here’s a screen capture of project in this repo in action.

Once you’ve cloned the repo, type gradle run in order to build and run this project on the command line.

Importing this project into Jetbrains IntelliJ IDEA

  • This project was created using Jetbrains Idea as a Gradle and Kotlin project (more info).
    • When you import this project into Idea as a Gradle project, make sure not to check “Offline work” (which if checked, won’t allow the gradle dependencies to be downloaded).
    • As of Jun 24 2018, Java 10 doesn’t work w/ this gradle distribution (v4.4.x), so you can use Java 9 or 8, or upgrade to a newer version of gradle (4.8+).

Undirected graphs

Here’s code in Kotlin that describes undirected graphs with and adjacency list to represent the edges. For more info, checkout this website. The adjacency list is stored in a MutableMap, which holds a LinkedList of nodes. A node / vertex in this graph can be of any class (T).

Here’s an image of an undirected graph.

/**
 * [More info](https://www.geeksforgeeks.org/graph-and-its-representations/).
 */
class Graph<T> {
    val adjacencyMap: MutableMap<T, MutableSet<T>> = mutableMapOf()

    fun addEdge(src: T, dest: T) {
        adjacencyMap[src] = adjacencyMap[src] ?: mutableSetOf()
        adjacencyMap[src]?.add(dest)
        adjacencyMap[dest] = adjacencyMap[dest] ?: mutableSetOf()
        adjacencyMap[dest]?.add(src)
    }

    override fun toString(): String = StringBuffer().apply {
        for (key in adjacencyMap.keys) {
            append("$key -> ")
            append(adjacencyMap[key]?.joinToString(", ", "[", "]\n"))
        }
    }.toString()
}

BFS

To do a breadth first traversal of the graph, here’s some code that uses a Queue (FIFO). The following implementation doesn’t use recursion, and also keeps track of the depth as it’s traversing the graph.

/**
 * Breadth first traversal leverages a [Queue] (FIFO).
 */
fun <T> breadthFirstTraversal(graph: Graph<T>, 
                              startNode: T, 
                              maxDepth: Int): String {
    // Mark all the vertices / nodes as not visited
    val visitedMap = mutableMapOf<T, Boolean>().apply {
        graph.adjacencyMap.keys.forEach { node -> put(node, false) }
    }
    // Keep track of the depth of each node, so that more than maxDepth
    // nodes aren't visited
    val depthMap = mutableMapOf<T, Int>().apply {
        graph.adjacencyMap.keys.forEach { node -> put(node, Int.MAX_VALUE) }
    }

    // Create a queue for BFS
    val queue: Deque<T> = LinkedList()

    // Initial step -> add the startNode to the queue
    startNode.also { node ->
        // Add to the tail of the queue
        queue.add(node)
        // Record the depth of this node
        depthMap[node] = 0
    }

    // Store the sequence in which nodes are visited, for return value
    val traversalList = mutableListOf<T>()

    // Traverse the graph
    while (queue.isNotEmpty()) {
        // Peek and remove the item at the head of the queue
        val currentNode = queue.remove()
        val depth = depthMap[currentNode]!!

        if (depth <= maxDepth) {

            if (!visitedMap[currentNode]!!) {

                // Mark the current node visited and add to traversal list
                visitedMap[currentNode] = true
                traversalList.add(currentNode)

                // Add nodes in the adjacency map
                graph.adjacencyMap[currentNode]?.forEach { node ->
                    // Add to the tail of the queue
                    queue.add(node)
                    // Record the depth of this node
                    depthMap[node] = depth + 1
                }

            }

        }

    }

    return traversalList.joinToString()
}

DFS

To do a depth first traversal of the graph, here’s some code that uses a Stack (LIFO).

/**
 * Depth first traversal leverages a [Stack] (LIFO).
 *
 * It's possible to use recursion instead of using this iterative 
 * implementation using a [Stack]. Also, this algorithm is almost
 * the same above, except for [Stack] is LIFO and [Queue] is FIFO.
 *
 * [More info](https://stackoverflow.com/a/35031174/2085356).
 */
fun <T> depthFirstTraversal(graph: Graph<T>, startNode: T): String {
    // Mark all the vertices / nodes as not visited
    val visitedMap = mutableMapOf<T, Boolean>().apply {
        graph.adjacencyMap.keys.forEach { node -> put(node, false) }
    }

    // Create a stack for DFS
    val stack: Deque<T> = LinkedList()

    // Initial step -> add the startNode to the stack
    startNode.also { node ->
        stack.push(node)
    }

    // Store the sequence in which nodes are visited, for return value
    val traversalList = mutableListOf<T>()

    // Traverse the graph
    while (stack.isNotEmpty()) {
        // Pop the node off the top of the stack
        val currentNode = stack.pop()

        if (!visitedMap[currentNode]!!) {

            // Store this for the result
            traversalList.add(currentNode)

            // Mark the current node visited and add to the traversal list
            visitedMap[currentNode] = true

            // Add nodes in the adjacency map
            graph.adjacencyMap[currentNode]?.forEach { node ->
                stack.push(node)
            }

        }

    }

    return traversalList.joinToString()
}

BFS and DFS traversal for binary trees

To see a similar implementation of BFS and DFS traversal for binary trees, please refer to the Binary-Trees tutorial.

Stacks and Queues

To learn more about stacks and queues, please refer to the Queues tutorial.

Resources

CS Fundamentals

Data Structures

Math

Big-O Notation

Kotlin

Markdown utilities

Related Posts