If you're looking to traverse a graph, there are two main algorithms you can use: Breadth-First Search (BFS) and Depth-First Search (DFS). In this post, we'll dive into both of these algorithms and explore how they work.

Breadth-First Search (BFS)

What is BFS?

Breadth-First Search is a graph traversal algorithm that visits all the vertices of a graph or tree iteratively, from a given starting vertex, by exploring all the neighboring nodes at the current depth before moving on to the nodes at the next depth. BFS starts at the root node (or any arbitrary node in the graph) and explores all the nodes at the same level before moving to the nodes at the next level.

BFS Algorithm:

The BFS algorithm is iterative in nature and can be implemented using a queue. Here's the BFS algorithm in pseudocode:

bfs(startVertex):
    create a queue and add the start vertex to it
    mark the start vertex as visited

    while the queue is not empty:
        dequeue the front node from the queue

        for each unvisited neighbor of the dequeued node:
            mark the neighbor as visited
            enqueue the neighbor to the queue

Here, we start by creating a queue and adding the starting vertex to it. We also mark the starting vertex as visited. Then, we continue to dequeue the nodes from the front of the queue and visit their unvisited neighbors by marking them as visited and adding them to the back of the queue.

BFS Example:

Let's take an example to understand how BFS works. Consider the following graph:

	 A
 /   \\
B     C
| \\   |
D  E  F

If we start the BFS algorithm from the vertex A, the traversal order will be A -> B -> C -> D -> E -> F.

BFS Implementation in Kotlin:

Now let's see how to implement the BFS algorithm in Kotlin using an adjacency list representation of the graph.

class Graph(private val adjacencyList: Map<String, List<String>>) {
    fun bfs(startVertex: String) {
        val queue: Queue<String> = LinkedList<String>()
        val visited = mutableSetOf<String>()

        queue.add(startVertex)
        visited.add(startVertex)

        while (queue.isNotEmpty()) {
            val currentVertex = queue.remove()
            println(currentVertex)

            adjacencyList[currentVertex]?.forEach {
                if (!visited.contains(it)) {
                    visited.add(it)
                    queue.add(it)
                }
            }
        }
    }
}

fun main() {
    val graph = Graph(
        mapOf(
            "A" to listOf("B", "C"),
            "B" to listOf("A", "D", "E"),
            "C" to listOf("A", "F"),
            "D" to listOf("B"),
            "E" to listOf("B"),
            "F" to listOf("C")
        )
    )

    graph.bfs("A")
}

In this implementation, we start by creating a Graph class that takes an adjacency list as input. The bfs() function takes a starting vertex as input and explores the graph using the BFS algorithm. We also maintain a queue to keep track of the nodes to be visited next and a set to keep track of already visited vertices.

In the bfs() function, we first add the starting vertex to the queue and mark it as visited. Then, we continue to dequeue the nodes from the front of the queue and visit their unvisited neighbors by marking them as visited and adding them to the back of the queue.

In the main() function, we create a Graph object with the input adjacency list and start the BFS algorithm from the vertex A.

Depth-First Search (DFS)

What is DFS?

Depth-First Search is a graph traversal algorithm that visits all the vertices of a graph or tree recursively, from a given starting vertex, by exploring as far as possible along each branch before backtracking. DFS starts at the root node (or any arbitrary node in the graph) and explores as far as possible along each branch before backtracking. In other words, DFS traverses the depth of any particular path before moving to the next path.

DFS Algorithm:

The DFS algorithm is recursive in nature and can be implemented using a stack. Here's the DFS algorithm in pseudocode:

dfs(vertex):
    if vertex is visited:
        return
    
    mark vertex as visited
    
    for each neighbor of vertex:
        dfs(neighbor)

Here, we start by checking whether the current vertex is already visited or not. If it's not visited, we mark it as visited and explore all its unvisited neighbors by recursively calling the dfs() function.

DFS Example:

Let's take an example to understand how DFS works. Consider the following graph:

	 A
 /   \\
B     C
| \\   |
D  E  F

If we start the DFS algorithm from the vertex A, the traversal order will be A -> B -> D -> E -> C -> F.

DFS Implementation in Kotlin:

Now let's see how to implement the DFS algorithm in Kotlin using an adjacency list representation of the graph.

class Graph(private val adjacencyList: Map<String, List<String>>) {
    private val visited = mutableSetOf<String>()

    fun dfs(vertex: String) {
        visited.add(vertex)
        println(vertex)

        adjacencyList[vertex]?.forEach {
            if (!visited.contains(it)) {
                dfs(it)
            }
        }
    }
}

fun main() {
    val graph = Graph(
        mapOf(
            "A" to listOf("B", "C"),
            "B" to listOf("A", "D", "E"),
            "C" to listOf("A", "F"),
            "D" to listOf("B"),
            "E" to listOf("B"),
            "F" to listOf("C")
        )
    )

    graph.dfs("A")
}

In this implementation, we start by creating a Graph class that takes an adjacency list as input. The dfs() function takes a starting vertex as input and explores the graph using the DFS algorithm. We also maintain a visited set to keep track of already visited vertices.

In the dfs() function, we first mark the current vertex as visited and print it. Then, we explore its neighbors by recursively calling the dfs() function on each unvisited neighbor.

In the main() function, we create a Graph object with the input adjacency list and start the DFS algorithm from the vertex A.