Paghahanap na lalim-muna

Paghahanap na lalim-muna
	Order in which the nodes get expandedOrder in which the nodes are visited
Class	Search algorithm
Data structure	Graph
Worst case performance	for explicit graphs traversed without repetition, for implicit graphs with branching factor b searched to depth d
Worst case space complexity	if entire graph is traversed without repetition, O(longest path length searched) for implicit graphs without elimination of duplicate nodes

Ang Paghahanap na lalim-muna (Ingles: Depth-first search o DFS) ay isang algoritmo ng paglalakbay o paghahanap ng isang puno(tree), istrakturang puno o grapo. Ito ay nagsisimula sa ugat(na pumipili ng isang nodo bilang ugat sa grapo) at ginagalugad ng kasing layo sa kahabaan ng bawat isang sanga bago ang pag-urong. Ang bersiyon ng paghahanap na lalim muna ay inimbestigahan noong ika-19 na siglo ng Pranses na matematikong si Charles Pierre Tremaux bilang stratehiya ng paglutas ng mga maze.

Order in which the nodes get expanded Order in which the nodes are visited
Class	Search algorithm
Data structure	Graph
Worst case performance	$O(\|V\|+\|E\|)$ for explicit graphs traversed without repetition, $O(b^{d})$ 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