Mélységi keresés (algoritmus)

A Programozás Wiki wikiből

A mélységi keresés (depth-first search) egy olyan fabejárási algoritmus, amelly a fában a gyökértől kiindulva minden csúcsot bejárja. Az algoritmus lényege, hogy a fában igyekszik először a gyökértől távolabbi (mélyebb) csúcsokat átvizsgálni, és csak azután lép vissza a szomszédos és a korábbi csúcsokhoz.

Programozási nyelvekben a megvalósítás általában rekurzív függvénnyel, vagy veremmel lehetséges.

Mélységi fabejárási példa C++ ban:

#include <ostream>
using namespace std;
string depth_first( const Node & n, ostream & o ) {
   int i;
   o << n.value();
   for ( i=0; i<n.childcount(); ++i )
      depth_first( n.child(i), o );
}