DFS si sortare topologica

Parcurgerea in adancime (Depth-First Search - DFS) porneste de la un nod dat (nod de start), care este marcat ca fiind in curs de procesare. Se alege primul vecin nevizitat al acestui nod, se marcheaza si acesta ca fiind in curs de procesare, apoi si pentru acest vecin se cauta primul vecin nevizitat, si asa mai departe. In momentul in care nodul curent nu mai are vecini nevizitati, se marcheaza ca fiind deja procesat si se revine la nodul anterior. Pentru acest nod se cauta primul vecin nevizitat. Algoritmul se repeta pana cand toate nodurile grafului au fost procesate. In urma aplicarii algoritmului DFS asupra fiecarei componente conexe a grafului, se obtine pentru fiecare dintre acestea cate un arbore de acoperire (prin eliminarea muchiilor pe care nu le folosim la parcurgere). Pentru a putea reconstitui acest arbore, pastram pentru fiecare nod dat identitatea parintelui sau.
Pentru fiecare nod se vor retine: timpul descoperirii, timpul finalizarii, parintele si culoarea.
Algoritmul de explorare DFS nu este nici complet (cautare pe un subarbore infinit) nici optimal (nu gaseste nodul cu adancimea minima).

Dandu-se un graf orientat aciclic, sortarea topologica realizeaza o aranjare liniara nodurilor in functie de muchiile dintre ele. Orientarea muchiilor corespunde unei relatii de ordine de la nodul sursa catre cel destinatie. Astfel, daca (u,v) este una dintre muchiile grafului, u trebuie sa apara inaintea lui v in insiruire. Daca graful ar fi ciclic, nu ar putea exista o astfel de insiruire (nu se poate stabili o ordine intre nodurile care alcatuiesc un ciclu).
Sunt doi algoritmi cunoscuti pentru sortarea topologica: algoritmul bazat pe DFS (parcurgere DFS pentru determinarea timpilor si sortare descrescatoare in functie de timpul de finalizare) un alt algoritm este cel descris de Kahn.

Programul de mai jos realizeaza o parcurgere DFS si o sortare topologica bazata pe aceasta a unui graf citit dintr-un fisier (dat ca liste de adiacenta).


#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

struct Nod
{
int val;
int nrVecini;
int * vecini;
int culoare;
int parinte;
int tDescoperire;
int tFinal;
};

int n;
struct Nod * graf;

/* citeste lista de adiacenta din fisier */
void readData()
{
FILE * f;
int i, j;

f = fopen( "in2.txt","r" );
assert( f );

fscanf( f, "%d", &n );
graf = ( struct Nod * ) malloc ( n * sizeof( struct Nod ) );

for ( i = 0; i < n; ++i ) {
graf[i].val = i;
fscanf( f, "%d", &graf[i].nrVecini );
graf[i].vecini = ( int * ) malloc ( graf[i].nrVecini * sizeof ( int ) );
for ( j = 0; j < graf[i].nrVecini; ++j )
fscanf( f, "%d", &graf[i].vecini[j] );
graf[i].parinte = -1;
graf[i].culoare = 0;
graf[i].tDescoperire = -1;
graf[i].tFinal = -1;
}
fclose( f );
}

/* afisarea timpilor din alg DFS*/
void printTimpi()
{
int i;
printf( "\n" );
for ( i = 0; i < n; ++i )
printf ( "Nod %d: descoperit la t=%d, explorat la t=%d \n", i, graf[i].tDescoperire, graf[i].tFinal );
printf( "\n" );
}

int timp = 0;

/* parcurgere DFS a grafului */
void explorare(int u) {

graf[u].tDescoperire = timp++;
graf[u].culoare = 1;
int j;
for(j = 0 ; j < graf[u].nrVecini ; j++) {
int x = graf[u].vecini[j];
if(graf[x].culoare ==0) {
graf[x].parinte = u;
explorare(x);
}
}
graf[u].culoare = 2;
graf[u].tFinal = timp++;

}

void DFS ()
{
int i;
for (i=0; i < n ; i++)
if(graf[i].culoare == 0)
explorare(i);
}



/* sortare topologica */
void topSort()
{
int ok = 0,i,j;
struct Nod aux;
while (ok == 0) {
ok = 1;
for(i=0; i < n-1;i++)
if(graf[i].tFinal < graf[i+1].tFinal) {
ok = 0; aux = graf[i]; graf[i]=graf[i+1]; graf[i+1]=aux; }
}
}

int main(void){
int i;

//incarca graful din fisier
readData();

//parcurgere BFS
DFS();

//afisarea timpilor
printTimpi();

//sortare topologica
topSort();
printf( "Sortare topologoca: " );
for ( i = 0; i < n; ++i )
printf ( "%d ", graf[i].val );
printf("\n");

for( i = 0; i < graf[i].nrVecini; ++i )
free(graf[i].vecini);
free(graf);
return 0;
}