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.
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
1 procedure DFS(G,v):
2 label v as explored
3 for all edges e in G.incidentEdges(v) do
4 if edge e is unexplored then
5 w ← G.opposite(v,e)
6 if vertex w is unexplored then
7 label e as a discovery edge
8 recursively call DFS(G,w)
10 label e as a back edge
No hay comentarios:
Publicar un comentario