Paghahanap na lalim-muna

Paghahanap na lalim-muna

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

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.

Graph and tree search algorithms
Alpha-beta pruning A* B* Beam Bellman–Ford algorithm Best-first Bidirectional Borůvka's algorithm Breadth-first D* Depth-first Depth-limited Dijkstra's algorithm Floyd–Warshall algorithm Hill climbing Iterative deepening depth-first Kruskal's algorithm Johnson's algorithm Lexicographic breadth-first Uniform-cost more
Related topics
Dynamic programming Search games