DFS in Kotlin. Depth First Search

DFS stands for Depth-First Search. It is a graph traversal algorithm that starts at a given source vertex and explores as far as possible along each branch before backtracking. In other words, it explores the vertices of a graph in depth-first order until there are no more vertices left to explore.

To implement DFS, we can use either a recursive or an iterative approach. In the recursive approach, we start by visiting the source vertex and then recursively visit each of its unvisited neighbors. In the iterative approach, we use a stack to keep track of the vertices to be visited and their unvisited neighbors.

DFS is commonly used for solving problems that involve searching or traversing a graph or a tree, such as finding the shortest path between two nodes or checking if a graph is connected. However, it may not always be the most efficient algorithm to use for large graphs with many branches or cycles.

class Graph(private val vertices: Int) {
    private val adjacencyList = mutableListOf<MutableList<Int>>()

    init {
        for (i in 0 until vertices) {
            adjacencyList.add(mutableListOf())
        }
    }

In this code, we first define a Graph class that represents an undirected graph using an adjacency list. The Graph class has a vertices field that stores the number of vertices in the graph, and an adjacencyList field that is a list of lists that stores the adjacency list for each vertex.

fun addEdge(u: Int, v: Int) {
    adjacencyList[u].add(v)
    adjacencyList[v].add(u)
}

We then define an addEdge method that adds an edge between two vertices to the adjacency list.

fun dfs(start: Int, visited: BooleanArray) {
    visited[start] = true
    print("$start ")

    for (v in adjacencyList[start]) {
        if (!visited[v]) {
            dfs(v, visited)
        }
    }
}
}

The dfs method is the heart of the DFS algorithm. It takes in the starting vertex and a visited array that keeps track of which vertices have been visited. We start by marking the starting vertex as visited and print its value. Then, for each adjacent vertex of the starting vertex, we recursively call the dfs method on it if it hasn’t been visited before.

class Graph(private val vertices: Int) {
    private val adjacencyList = mutableListOf<MutableList<Int>>()

    init {
        for (i in 0 until vertices) {
            adjacencyList.add(mutableListOf())
        }
    }

    fun addEdge(u: Int, v: Int) {
        adjacencyList[u].add(v)
        adjacencyList[v].add(u)
    }

    fun dfs(start: Int, visited: BooleanArray) {
        visited[start] = true
        print("$start ")

        for (v in adjacencyList[start]) {
            if (!visited[v]) {
                dfs(v, visited)
            }
        }
    }
}

fun main() {
    val graph = Graph(5)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 3)
    graph.addEdge(3, 4)

    val visited = BooleanArray(5)
    println("DFS Traversal:")
    graph.dfs(0, visited)
}

Finally, in the main function, we create a new Graph object with 5 vertices and add edges between them using the addEdge method. We also create a visited array of booleans with the same length as the number of vertices in the graph. We then call the dfs method on the starting vertex 0 and pass in the visited array. The output will be the DFS traversal of the graph starting from vertex 0.