Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking.
DFS-iterative(G,v):
{
let S be a stack
S.push(v)
while S is not empty
{
v = S.pop()
if v is not labeled as discovered:
{
label asdiscovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
}
}
}
DFS output : A, B, D, F, E, C, G
.
DFS-iterative(G,v):
{
let S be a stack
S.push(v)
while S is not empty
{
v = S.pop()
if v is not labeled as discovered:
{
label asdiscovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
}
}
}
DFS output : A, B, D, F, E, C, G