Graphs

• Undirected graphs
  • BFS
  • DFS
• Stacks and Queues

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 adjacencyList: MutableMap<T, MutableSet<T>> = mutableMapOf()

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

    override fun toString(): String = StringBuffer().apply {
        for (key in adjacencyList.keys) {
            append("$key -> ")
            append(adjacencyList[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.adjacencyList.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.adjacencyList.keys.forEach { node -> put(node, Int.MAX_VALUE) }
    }

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

    // Init step - mark the current node as visited and add it to the tail of
    // the queue
    startNode.also { node ->
        // Add to the tail of the queue
        queue.add(node)
        // Mark it as visited
        visitedMap[node] = true
        // Record the depth of this node
        depthMap[node] = 0
    }

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

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

        // Check to make sure maxDepth is respected
        if (depthMap[currentNode]!! <= maxDepth) {

            // Get all the adjacent vertices of the node. For each of them:
            // - If an adjacent has not been visited then mark it visited
            // - Add it to the back of the queue
            val adjacencyList = graph.adjacencyList[currentNode]
            adjacencyList?.forEach { adjacentNode ->
                val adjacentNodeHasBeenVisited = visitedMap[adjacentNode]!!
                if (!adjacentNodeHasBeenVisited) {
                    // Add adjacent node to the tail of the queue
                    queue.add(adjacentNode)
                    // Mark adjacent node as visited
                    visitedMap[adjacentNode] = true
                    // Record the depth of this node
                    depthMap[adjacentNode] = depthMap[currentNode]!! + 1
                }
            }

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

        }

    }

    return result.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> dfs_traversal(graph: Graph<T>, startNode: T): String {
    // Mark all the vertices / nodes as not visited
    val visitedNodeMap = mutableMapOf<T, Boolean>().apply {
        graph.adjacencyList.keys.forEach { node -> put(node, false) }
    }

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

    // Init step - mark the current node as visited and push it to
    // the top of the stack
    startNode.also { node ->
        stack.push(node)
        visitedNodeMap[node] = true
    }

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

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

        // Get all the adjacent vertices of the node. For each of them:
        // - If an adjacent has not been visited then mark it visited
        // - Add it to the top of the stack (push it to the top)
        val adjacencyList = graph.adjacencyList[currentNode]
        adjacencyList?.forEach { adjacentNode ->
            val adjacentNodeHasBeenVisited = visitedNodeMap[adjacentNode]!!
            if (!adjacentNodeHasBeenVisited) {
                visitedNodeMap[adjacentNode] = true
                stack.push(adjacentNode)
            }
        }

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

    return result.joinToString()
}

Recursive implementation

For a recursive implementation of BFS and DFS traversal, please refer to the Binary-Trees page.

Stacks and Queues