Depth first search (DFS)

Algorithms #algorithms #dfs #graphs

Depth First Search (DFS)

Depth First Search (DFS) is a popular algorithm for traversing and searching a graph data structure. It is a systematic method for visiting all the vertices of a graph in a depth-first manner, which means that it explores as far as possible along each branch before backtracking.

The basic idea behind DFS is to start at a source vertex and explore each vertex as far as possible along each branch before backtracking. When there are no more vertices to be visited, the algorithm moves to the next unvisited vertex and repeats the process. This continues until all vertices have been visited.

Implementation

The algorithm can be implemented using either recursion or a stack data structure.

Recursion

In a recursive implementation, the function calls itself for each unvisited vertex that is adjacent to the current vertex. The function continues to call itself until all vertices have been visited.

Stack

In a stack implementation, the algorithm uses a stack data structure to keep track of the vertices that need to be visited. The algorithm pushes the current vertex onto the stack and then explores each unvisited vertex that is adjacent to it. The algorithm continues to explore vertices until there are no more vertices to be visited, at which point it pops the last vertex from the stack and continues exploring from that vertex.

Advantages

Ease of Implementation: DFS is relatively easy to implement. This makes it a popular choice for many problems that involve graph traversal.
Linear Time Complexity: The time complexity of DFS is linear in the number of vertices and edges in the graph. This makes it suitable for large graphs, where other algorithms with higher time complexity would not be practical.
Flexibility: DFS can be easily adapted to solve different problems by changing the way vertices are processed or the order in which they are explored. e.g. finding cycles in undirected graph.
Suitable for Finding Paths: DFS is particularly useful for finding paths between vertices in a graph. By starting the search at the source vertex and following a path to the destination vertex, it is possible to find a path between two vertices in a graph.
Suitable for Finding Connected Components: DFS can be used to find the connected components in an undirected graph. This is because the algorithm starts at a vertex, explores all vertices reachable from it, and then backtracks.
Suitable for Topological Sorting: DFS can be used to perform a topological sort of a directed acyclic graph (DAG). This is because the algorithm explores vertices in a depth-first manner and visits vertices in the order in which they can be processed.

Example

This sample code performs a DFS on the graph above.

fun main() {
    val adjacencyMap = mutableMapOf(
        0 to listOf(1, 2),
        1 to listOf(0, 2),
        4 to listOf(5, 8),
        2 to listOf(7, 1, 0, 3),
        5 to listOf(8, 4),
        6 to listOf(3, 9, 10),
        3 to listOf(2, 6),
        11 to listOf(),
        7 to listOf(2, 5),
        8 to listOf(4, 5),
        10 to listOf(6, 11),
        9 to listOf(6, 11)
    )

    depthFirstSearch(adjacencyMap)
}

//sampleStart
fun depthFirstSearch(adjacencyMap: Map<Int, List<Int>>) {
    // click + to see full script

    // store a boolean value for each vertex, true if visited false otherwise
    val visitedVertices = BooleanArray(adjacencyMap.size)

    fun dfs(vertex: Int) {
        // print visited vertex
        print(" $vertex")

        // mark vertex as visited
        visitedVertices[vertex] = true

        /**
         * iterate over adjacent vertices and start DFS if
         * vertex is not already visited
         */
        adjacencyMap.getValue(vertex).forEach { adjacentVertex ->
            if (visitedVertices[adjacentVertex].not()) {
                dfs(adjacentVertex)
            }
        }
    }

    /**
     * Iterate over all the vertices and start DFS, if vertex
     * is not already visited
     */
    for (vertex in adjacencyMap.keys) {
        if (visitedVertices[vertex].not()) {
            dfs(vertex)
        }
    }
}
//sampleEnd

multixlab

Depth first search (DFS)