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 );
}

DFS stack-kel összefüggő gráfon:

#include <iostream>
#include <vector>
#include <stack>
size_t N;
std::vector<std::vector<size_t> > adj;

void dfs(int root)
{
    std::vector<bool> v(N,0);
    std::stack<size_t> q;
    q.push(root);
    while(!q.empty())
    {
        size_t n=q.top();
        q.pop();
        if(v[n])
            continue;
        std::cout << "at " << n << std::endl;
        v[n]=1;
        for(size_t i=0; i<adj[n].size(); ++i)
            if(!v[adj[n][i]])
                q.push(adj[n][i]);
    }
}

main()
{
    // gráf definiálása, azaz N és az éllista feltöltése.
    // adj.size=N, 0<=adj[n][i]<N
    // ..

    dfs(0);
}

Példákód Python nyelven, veremmel.

def bejar(kcsucs, n):
 vm = 0 # verem mutató
 verem = [0]*n*2 # verem
 bejart = [0]*n # a bejárt csúcsok tárolása
 x = kcsucs # x, az aktuális csúcs; kezdőértéke a függvénynek adott érték
 i = 0 # bejártlan csúcsok kereséséhez használt változó
 kesz = False # nem jártuk be a gráfot
 print(x+1) # kiírjuk a csúcsot, ahonnan indulunk
 while kesz != True: # amíg nincs kész a bejárás
  while(i<n and (graf[x][i] != 1 or bejart[i] == 1 or i == x)):
   i+=1 # következő be nem járt csúcs megkeresése
  if i < n: # ha ez a feltétel teljesül, akkor még van bejártlan csúcs
   verem[vm] = x # aktuális csúcs eltárolása a veremben
   vm+=1 # verem mutató +1
   bejart[x] = 1 # adott csúcsnál már jártunk
   verem[vm] = i # a következő be nem járt csúcs tárolása
   vm+=1 # verem mutató +1
   x = i # az aktuális csúcsot átállítjuk a "megtalált" és még be nem járt csúcsra
   i = 0 # a kereséhez használt változót visszaállítjuk
   print(x+1) # kiírjuk, hogy melyik csúcsnál vagyunk (a plusz egy a Python tömbindexelése miatt kell, mivel nullával kezdődik)
  elif vm > 0: # ha a verem mutató nulla lenne, akkor visszaértünk volna a kezdőcsúcshoz
   bejart[x] = 1 # az aktuális csúcs nem kapcsolódik több bejáratlan csúcshoz; tehát ezt a csúcsot teljesen bejáratuk
   vm-=1 # verem mutató -1
   i = verem[vm]+1 # a mostani, már bejárt csúcs kivétele; a plusz egy a végtelen ciklus elkerülése miatt kell
   vm-=1 # verem mutató csökkentése
   x = verem[vm] # a mostani, már bejárt csúcs "szülő csúcsát" kivesszük a veremből és azon folytatjuk a még be nem járt csúcsok keresését
   print(x+1) # kiírjuk, hogy melyik csúcsnál vagyunk
  else: # verem mutató <=0, tehát visszaértünk a kezdőcsúcshoz
   kesz = True # végeztünk a bejárással

# PÉLDA:
n = 6 # csúcsok száma
graf = [[0,1,1,0,0,0], # csúcsmátrix
        [1,0,0,1,1,0],
        [1,0,0,0,0,1],
        [0,1,0,0,0,0],
        [0,1,0,0,0,0],
        [0,0,1,0,0,0]]
bejar(0, n) # bejárás elkezdése

Csak a függvény, magyarázatok nélkül

def bejar(kcsucs, n):
 vm = 0
 verem = [0]*n*2
 bejart = [0]*n
 x = kcsucs
 i = 0
 kesz = False
 print(x+1)
 while kesz != True:
  while(i<n and (graf[x][i] != 1 or bejart[i] == 1 or i == x)):
   i+=1
  if i < n:
   verem[vm] = x
   vm+=1
   bejart[x] = 1
   verem[vm] = i
   vm+=1
   x = i
   i = 0
   print(x+1)
  elif vm > 0:
   bejart[x] = 1
   vm-=1
   i = verem[vm]+1
   vm-=1
   x = verem[vm]
   print(x+1)
  else:
   kesz = True