Artificial intelligence‎ > ‎Graph‎ > ‎

Depth-first search

We have to go deeper

Depth-first search is a algorithm for traversing a graph structure. It starts with the edges from the start node and explore them as long as possible before backtracking. It can be used both to visit all the nodes or the search for a specific node.

Algorithm
    Put start node onto stack.
    Get node from stack until stack is empty.
        If node not explored flag it and add all its linked nodes to the stack.
    If stack is empty then no result was found.

Pseudocode
function DFS(g, v)
    stack s.push(v)

    while !s.empty()
        v s.pop()
        if !v.explored
            v.explored = true
            foreach each edge e in v
                s.push(e.tonode)
Comments