Order in which the nodes are visited

DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn't finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.

Worst case performance: O( | V | + | E | ) for explicit graphs traversed without repetition, O(bd) for implicit graphs with branching factor b searched to depth d.

Worst case space complexity: O( | V | ) if entire graph is traversed without repetition, O(longest path length searched) for implicit graphs without elimination of duplicate nodes.

## Pseudocode

**Input**: A graph *G* and a vertex *v* of G

**Output**: A labeling of the edges in the connected component of v as discovery edges and back edges

1procedureDFS(G,v):

2 labelvas explored

3for alledges e in G.incidentEdges(v)do

4ifedgeeis unexploredthen

5w← G.opposite(v,e)

6ifvertexwis unexploredthen

7 labeleas a discovery edge

8 recursively call DFS(G,w)

9else

10 labeleas a back edge

## No hay comentarios:

## Publicar un comentario