Grafuri. parcurgerea grafurilor. Sortarea topologică

Scop:

Parcurgerea in latime se foloseste:

- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA);

- intr-o multime de aplicatii din teoria grafurilor (in special legate de drum minim de la un nod dat la un alt nod, componente conexe, grafuri bipartite);

- in jocuri pe calculator, pentru gasirea drumurilor, in special in jocuri Real Time Strategy (un mic exemplu in aplicatie);

Parcurgerea in adancime se foloseste:

- pentru Inteligenta Artificiala (metoda neinformata de cautare... mai multe la cursul de IA), insa combinarea sa cu euristici poate fi mai fructuoasa decat la parcurgerea in latime;

- sortarea topologica si alte aplicatii cu grafuri legate de componente conexe si tare conexe.

1. Intro:

Def.: Graful este o pereche de multimi G=(V,E). Multimea V contine nodurile grafului (vertices), iar multimea E contine muchiile (edges) sale, fiecare muchie stabilind o relatie de vecinatate intre doua noduri.

O parcurgere isi propune sa ia in discutie fiecare nod al grafului exact o singura data, pornind de la un nod ales, numit in continuare nod sursa.

Parcurgerea in latime viziteaza intai toti vecinii unui nod dat si numai dupa ce epuizeaza toti vecinii trece la un alt nod. Parcurgerea in adancime isi propune sa mearga din vecin in vecin al vecinului cat de mult poate, „adancindu-se” astfel in structura grafului.

2. Parcurgerea in latime (Breadth First Search, BFS):

2.1. Teoria

Parcurgerea in latime foloseste o coada (Q) intr-un mod asemanator celui folosit de algoritmul AC-3. Initial in aceasta coada se gaseste doar nodul sursa. Vizitand pe rand vecinii sai ii adaugam si pe ei in coada. La sfarsit, dupa ce nu mai sunt vecini ai sursei nevizitati, scoatem nodul sursa din coada.

Pentru fiecare din nodurile prezente in coada, aplicam procedura de mai sus. Atentie insa: vizitand vecinii unui nod trebuie sa verificam ca acestia nu au mai fost deja vizitati (adica sunt inca albi).

In afara de coada q mai sunt necesare sau utile cateva structuri de date.

a) Putem diferentia intre nodurile nevizitate, cele asezate in coada si cele complet prelucrate printr-un vector denumit culoare:

c[nod] = alb, daca nodul nu a fost vizitat

gri, daca nodul a fost vizitat si asezat in q

negru, daca nodul a fost prelucrat si scos din q

b) Un vector d (distanta) care sa retina distanta (in numar de muchii) fata de sursa se poate dovedi util in unele probleme.

c) Vectorul de parinti p este necesar pentru a reface drumul de la sursa la un alt nod dupa parcurgere.