# Algorithms in Kotlin, Graphs, Part 5/7

## 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

- Brilliant.org CS Foundations
- Radix sort
- Hash tables
- Hash functions
- Counting sort
- Radix and Counting sort MIT

### Data Structures

### Math

- Khan Academy Recursive functions
- Logarithmic calculator
- Logarithm wikipedia
- Fibonacci number algorithm optimizations
- Modulo function

### Big-O Notation

- Asymptotic complexity / Big O Notation
- Big O notation overview
- Big O cheat sheet for data structures and algorithms

### Kotlin

- Using Jetbrains Idea to create Kotlin and gradle projects, such as this one
- How to run Kotlin class in Gradle task
- Kotlin
`until`

vs`..`

- CharArray and String