Depth-first search

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)