⌘Ctrlk

🤖depth-first search

🚧 under construction

Depth-First Search (DFS)

visits a graph node and explores its child nodes or branches before proceeding to the next node. (going deep first before going wide)

a recursive algorithm that leverages the stack.

// code

// pseudo code
dfs(Graph G, GraphNode root) {

    // base case
    if (root is null) return
 
    // mark root as visited
    root.visited = true
 
    for (neighbors n of root in G)
        if (n is not yet visited)
            dfs(G, n) // recursive call
}

Previousbreadth-first search NextGraph examples

Last updated 3 years ago