Gráfkereső algoritmus

A gráfkereső algoritmus egy olyan keresőrendszer, amely a backtrack algoritmussal szemben az összes lehetséges utat nyilvántartja egy keresőfa segítségével. Egy másik szokásos elnevezés ezen algoritmusra a Keresőfával Kereső.

Adatbázis:

Tetszőleges reprezentációs gráf már bejárt részét kifeszítő fa. Ezt a fát csomópontokkal tartjuk nyilván amelyekben az alábbi információkat tároljuk:

• A helyet, amelyet az adott csúcs reprezentál.
• Egy mutatót amely megmutatja, hogy az aktuális csúcsot melyik csúcsból értük el.
• Azt a lépést, amellyel elértük a csúcsot.

Nyilvántartjuk ezen kívül a csúcsok státuszát, ami a következők egyike lehet:

• Nyílt: Az adott csúcsot ugyan elértük már a keresés során, de nem vizsgáltuk a csúcsból közvetlenül elérhető helyeket.
• Zárt: Az innen egy lépéssel elérhető csúcsokat már vizsgáltuk a keresés során.

Algoritmus:

Az algoritmus lényege, hogy kiterjesztjük az ismert csúcsok körét addig, amíg egy célcsúcsot el nem érünk.

A Kiterjeszt eljárás segítségével felépítjük a reprezentációs gráf már bejárt részét feszítő fát. Ezen eljárás feladata egy nyílt csomópont azon szomszédainak felfűzése a fába amik még nem szerepelnek benne.

  procedure Kiterjeszt(Gráf, Csúcs, Nyíltak, Zártak) 
     FOR EACH Újlépés IN Lépések( Gráf, Csúcs ) LOOP 
        IF (NOT Újépés.Cél IN Nyíltak) AND (NOT Újlépés.Cél IN Zártak) THEN  
           Új <- (Hely=Újlépés.Cél, Előző=Csúcs, Lépés=Újlépés)
           Nyíltak.Add(Új) 
        ENDIF 
     END LOOP 
     Csúcs.Státusz <- Zárt 
     Zártak.Add(Csúcs) 
     Nyíltak.Remove(Csúcs) 
  END

Az algoritmus második és egyben fő része tekinthető egyfajta vezérlőnek is.

  Procedure Keresőfával_Kereső(Gráf, Kezdőcsúcs, Célcsúcsok) 
     Csomópont <- (Hely=Kezdőcsúcs, Előző=NULL, Lépés=NULL)
     Nyíltak.Add(Csomópont) 
     Zártak <- ÜRES 
     WHILE(TRUE) DO 
        IF Nyíltak IS NULL THEN 
           BREAK  
        ENDIF 
        Csomópont <- Nyiltak[Random] 
        IF Csomópont.Hely IS IN Célcsúcsok THEN 
           BREAK 
        ENDIF 
        Kiterjeszt(Gráf, Csomópont, Nyíltak, Zártak) 
     END DO 
     IF Nyíltak IS NOT NULL THEN 
        Kiír(Csomópont) 
     ELSE 
        Kiír("Nincs megoldás") 
     ENDIF 
  END

A kereső tetszőleges véges reprezentációs gráfban talál megoldást amennyiben létezik. Ha nem létezik megoldás akkor ezt felismeri a Nyílt státuszú csúcsok elfogyásával.

C++

Azaz egy kezdőpontból tetszőleges módon bejárjuk a gráfot, tetszőleges számú célpont bármelyikét elérve leállunk, szeretnénk rekonstruálni az oda vezető utat.

size_t N;
std::vector<std::vector<size_t> > adj;
typedef std::pair<size_t,size_t> pzz;

void dfs(size_t s, std::vector<bool> const &t)
{
    std::stack<pzz> q;
    std::vector<size_t> b(N,N);
    q.push(pzz(s,s));
    while(!q.empty())
    {
        size_t p=q.top().first;
        size_t n=q.top().second;
        q.pop();
        if(b[n]<N)
            continue;
        b[n]=p;
        if(t[n])
        {
            std::vector<size_t> w(1,n);
            for(size_t i=n; b[i]!=i; i=b[i])
                w.push_back(b[i]);
            std::cout << "egy útvonal " << s << " és " << n << " között: (";
            for(size_t i=w.size(); i--;)
                std::cout << w[i] << (i?",":"");
            std::cout << ")" << std::endl;
            return;
        }
        for(size_t i=0; i<adj[n].size(); ++i)
            if(b[adj[n][i]]==N)
                q.push(pzz(n,adj[n][i]));
    }
    std::cout << "a kezdőpontból egyik célpont sem elérhető" << std::endl;
}