BFS intr-un graf

Parcurgerea in latime (Breadth-first Search - BFS) este un algoritm de cautare in graf, in care, atunci cand se ajunge intr-un nod oarecare, v, nevizitat, se viziteaza toate nodurile nevizitate adiacente lui v, apoi toate varfurile nevizitate adiacente varfurilor adiacente lui v, etc.
BFS depinde de nodul de start. Plecand dintr-un nod se va parcurge doar componenta conexa din care acesta face parte. Pentru grafuri cu mai multe componente conexe se vor obtine mai multi arbori de acoperire.
In urma aplicarii algoritmului BFS asupra fiecarei componente conexe a grafului, se obtine un arbore de acoperire (prin eliminarea muchiilor pe care nu le folosim la parcurgere). Pentru a putea reconstitui acest arbore, se pastreaza pentru fiecare nod dat identitatea parintelui sau. In cazul in care nu exista o functie de cost asociata muchiilor, BFS va determina si drumurile minime de la radacina la oricare
nod.
Pentru implementarea BFS se foloseste o coada. In momentul adaugarii in coada, un nod trebuie colorat gri (a fost descoperit si urmeaza sa fie prelucrat).
Algoritmul de explorare BFS este complet si optimal.

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

#define START 0
#define FINISH 2
#define INF 10000

struct Nod
{
int nrVecini;
int * vecini;
int culoare;
int parinte;
};

int n;
struct Nod * graf;

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

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

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

for ( i = 0; i < n; ++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;
}
fclose( f );
}

void printRoad()
{
int aux = FINISH;
printf( "Drumul de la finish la start: " );
while ( aux != START ) {
printf ( "%d ", aux );
if ( graf[aux].parinte>=0 ) {
aux = graf[aux].parinte;
} else {
printf("\nEroare. nu se cunoaste parintele nodului %d\n", aux );
return;
}
}
printf ( "%d\n", aux );
}

/* parcurgere BFS a grafului, plecand din nodul start */
void BFS ( int start )
{
int *dist =(int *)malloc(n*sizeof(int));
int i;
for (i=0; i < n; i++)
dist[i] = INF;
dist[start] = 0;
graf[start].culoare = 1;// gri
Queue Q = NULL;
int j;
enqueue (&Q, &start);
while (size(Q) > 0) {
i = *(int *)Front(Q);
for(j=0; j < graf[i].nrVecini; j++) {
int *x = (int *)malloc(sizeof(int));
*x = graf[i].vecini[j];
if(graf[*x].culoare == 0) { //alb
dist[*x]=dist[i]+1;
graf[*x].parinte = i;
graf[*x].culoare = 1; // gri
enqueue(&Q, x);
free (x);
}
}
graf[i].culoare = 2; //negru
dequeue (&Q);

}
printf("start %d finish %d \n", START, FINISH);
printf("distanta este %d\n", dist[FINISH]);
}

int main(void){
int i;

//incarca graful din fisier
readData();

//parcurgere BFS
BFS( START );

//afisarea nodurilor dintre finish si start
printRoad();

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

Algoritmi de dirijare

Problema dirijarii apare la nivelul retea, si consta in a determina calea pe care o vor parcurge pachetele de la calculatorul sursa la calculatorul destinatie. Software-ul nivelului retea trebuie sa asigure desfasurarea a doua procese distincte:

• retransmitere (forwarding): ceea ce se intampla cand un pachet ajunge la ruter, si acesta trebuie sa stabileasca, prin consultarea unei tabele de rutare, linia de iesire pe care va transmite pachetul mai departe
• dirijare (routing): este procesul de construire si actualizare a tabelei de rutare - adica de stabilire a cailor pe care vor fi transmise pachetele

Referitor la algoritmii ce tin de procesul de dirijare, putem distinge doua categorii de algoritmi: algoritmi neadaptivi (ce realizeaza o dirijare statica - toate rutele sunt determinate initial si nu se tine cont de modificarile ulterioare de trafic si topologie ce apar in retea) si algorimi adaptivi (rutele sunt modificate ca urmare a schimbarilor de topologie si de trafic din retea).

Dintre algoritmii neadaptivi fac parte:

• dirijarea pe calea cea mai scurta (shortest path routing): subreteaua este reprezentata ca un graf, in care ruterele sunt noduri, si se aplica un algoritm (de exemplu Dijkstra) pentru a determina caile cele mai scurte dintre noduri; se pot folosi diverse metrici, cum ar fi numarul de rute intermediare, distanta geografica, intarzierile medii de transmisie
• inundarea (flooding): ruterul trimite fiecare pachet receptionat pe toate liniile de iesire, in afara de cea pe care a venit pachetul; varianta: inundarea selectiva (selective flooding)

Algoritmii adaptivi cel mai des utilizati sunt:

• dirijarea cu vectori distanta (distance vector routing): fiecare ruter mentine o tabela cu calea cea mai buna pentru fiecare destinatie si linia de iesire corespunzatoare acestei cai; tabelele sunt actualizate pe baza informatiilor primite de la celelalte rutere
• dirijarea folosind starea legaturilor (link state routing): fiecare router determina costurile asociate cailor catre vecini, apoi trimite aceste informatii in toata subreteaua; dupa schimburile de informatii, fiecare ruter are informatii complete despre graf si poate determina caile minime

Exemple de protocoale de dirijare:

• RIP (Routing Internet Protocol) - utilizeaza algoritmul distance vector
• OSPF (Open Shortest Path First Protocol) - utilizeaza algoritmul link state
• BGP (Border Gateway Protocol)

Programul de mai jos citeste dintr-un fisier un numar n reprezentand dimensiunea unei matrici de adiacenta a unui graf cu nodurile retelei, precum si aceasta matrice. Initial creeaza o tabela de rutare pentru fiecare nod, care contine informatii despre toate nodurile retelei, sub forma : Destinatar , Cost (=valoarea asociata muchiei dintre acel nod si destinatar), Next_Hop (=nodul urmator de urmat pentru a ajunge la destinatar). Apoi, pentru fiecare nod se vor actualiza informatiile despre celelalte noduri combinand informatiile gasite in fiecare tabela de rutare cercetata.


#include "stdio.h"
#include "stdlib.h"
#define INF 1000

int **a, n;

typedef struct tabela {

int *dest;
int *cost;
int *next_hop;

} Tabela;

void printTabela(Tabela t) {

int i;
for(i=0; i < n; i++)
printf("%d\t%d\t%d \n", t.dest[i], t.cost[i], t.next_hop[i] );
}

int find_dest(Tabela t, int poz) { // prima dest incepand cu poz

int i=poz;
while(t.cost[i] == INF && i<=n-1)
i++;
if (i<=n-1)
return t.dest[i];
return -1; // nu a gasit
}

int main () {

FILE * f = fopen ("in", "r");
fscanf(f, "%d",&n);
int i,j,k;
a = (int **)malloc(n*sizeof(int));

for(i=0; i < n ; i++)
a[i] = (int *)malloc(n*sizeof(int));
for(i=0; i < n ; i++)
for(j=0; j < n ; j++)
fscanf(f, "%d", &a[i][j]);

Tabela * tab = (struct tabela *)malloc(sizeof(struct tabela)*n);
for(i=0; i < n ; i++) {
tab[i].dest = (int *)malloc(n*sizeof(int));
tab[i].cost = (int *)malloc(n*sizeof(int));
tab[i].next_hop = (int *)malloc(n*sizeof(int));
}

// constructia tabelei in forma initiala
for (i=0; i < n ; i++) { // pt fiecare tabela
for(j=0; j < n ; j++)
if (a[i][j]) {
tab[i].dest[j] = j;
if(i!=j)
tab[i].cost[j] = 1;
else
tab[i].cost[j] = 0;
tab[i].next_hop[j] = j;
}
else {
tab[i].dest[j] = j;
tab[i].cost[j] = INF;
tab[i].next_hop[j] = -1;
}
}

printf("Tabela 5 inainte de aplicarea algoritmului:\n");
printTabela(tab[5]); // printam un anumit nod


for(i=0; i < n ; i++) // pt fiecare tabela

for(j=0; j < n ; j++) { // pt fiecare destinatie din tabela
k = find_dest(tab[j],0);
while(k!=-1) {
if (tab[i].cost[k] > tab[j].cost[k] + tab[i].cost[j]) {
tab[i].cost[k] = tab[j].cost[k] + tab[i].cost[j];
tab[i].next_hop[k] = tab[j].dest[j];
}
k = find_dest(tab[j],k+1);
}
}

printf("Tabela finala 5 cu drumuri optime:\n");
printTabela(tab[5]);

return 0;

}

Purificarea retelelor Petri

In procesul de modelare a protocoalelor folosind RP, pot aparea retele impure. De exemplu, o tranzitie impura t are un loc de intrare l, care este simultan nod de iesire. Pentru o RP pura niciun loc nu este intrare si iesire a aceleiasi tranzitii. Se demonstreaza ca orice RP impura poate fi transformata intr-o RP pura prin reducere. Reducerea ei se face astfel:

- se suprima arcele (l, t) si (t, l)

- se suprima t daca ea devine izolata

Urmatorul program indeplineste urmatoarele functii:

• isi creeaza un exemplu de retea Petri folosind locuri si tranzitii
• verifica daca reteaua contine impuritati;
• aplica reducerea specificata asupra fiecarei tranzitii impure;
• in final printeaza reteaua purificata
  

#################################

#include"stdio.h"

typedef struct {
int pre[100];
int post[100];
int Npre,Npost;
} tran;

int main() {
tran t[6];

t[1].Npre=2;
t[1].Npost=2;
t[1].post[0]=1;
t[1].post[1]=2;
t[1].pre[0]=1;
t[1].pre[1]=2;

t[2].Npre=3;
t[2].Npost=1;
t[2].post[0]=3;
t[2].pre[2]=3;
t[2].pre[0]=1;
t[2].pre[1]=2;


t[3].Npre=1;
t[3].Npost=1;
t[3].post[0]=1;
t[3].pre[0]=3;

t[4].Npre=1;
t[4].Npost=1;
t[4].post[0]=2;
t[4].pre[0]=3;

t[5].Npre=1;
t[5].Npost=1;
t[5].post[0]=3;
t[5].pre[0]=3;

int n=5,ok=1,i,k,l;

do {
ok=1;
for(i=1;i<=n;i++)
for(k=0;k<=t[i].Npre-1 ; k++)
for(l=0; l<=t[i].Npost-1; l++)
if((t[i].pre[k]==t[i].post[l]) && (t[i].pre[k]!=0)) // daca a gasit tranzitie impura
{
ok=0;
t[i].pre[k]=t[i].post[l]=0; // purifica
break;
}
} while(ok==0);

for(i=1;i<=n;i++) {
printf("\nT%d:\nPre:",i);
for(k=0;k<=t[i].Npre-1;k++)
printf("%d ",t[i].pre[k]);
printf("\nPost:");
for(k=0; k<=t[i].Npost-1 ; k++)
printf("%d ",t[i].post[k]);
}

return 0;
}

Calcul de polinoame folosind cozi

#include "stdio.h"

#include "queue.h"

#include "stdlib.h"

typedef struct nod_pol{

double coef;

int exp;

} p_nod;

int main(){

Queue Q = NULL, P = NULL;

p_nod p[] = { {2,3},{23,2},{2,0},{34,3},{5,1},{3,2},{8,0}};

enqueue(&Q, &p[0]);

enqueue(&Q, &p[1]);

enqueue(&Q, &p[2]);

enqueue(&P, &p[3]);

enqueue(&P, &p[5]);

enqueue(&P, &p[4]);

enqueue(&P, &p[6]);

int i,j,k,m;

Queue aux1=Q , aux2 = P , suma = NULL, produs = NULL;

k = size(Q);

m = size(P);

int exp;

// adunarea a doua polinoame

p_nod y = *(p_nod*)dequeue(&aux1);

p_nod z = *(p_nod*)dequeue(&aux2);

if (y.exp>z.exp) exp = y.exp;

else exp = z.exp;

int exp2 = y.exp + z.exp;

for (j=exp;j>=0;j--){

aux1 = Q; aux2 = P;

p_nod *t = (p_nod*)malloc(sizeof(p_nod));

t->exp = j;

t->coef = 0;

for (i=0;i<=k-1;i++){

p_nod y = *(p_nod*)dequeue(&aux1);

if (y.exp==j) t->coef+=y.coef;

}

for (i=0;i<=m-1;i++){

p_nod z = *(p_nod*)dequeue(&aux2);

if (z.exp==j) t->coef+=z.coef;

}

enqueue(&suma,t);

}

k = size(suma);

for (i=0;i<=k-1;i++){

z = *(p_nod*)dequeue(&suma);

printf("%.2lf %d\n",z.coef,z.exp);

}

printf("\n");

// inmultirea a doua polinoame

for (j=exp2; j>=0; j--){

p_nod *t = (p_nod*)malloc(sizeof(p_nod));

t->exp = j;

t->coef = 0;

aux1 = Q;

while (aux1!=NULL){

aux2 = P;

p_nod y = *(p_nod*)dequeue(&aux1);

while (aux2!=NULL){

p_nod z = *(p_nod*)dequeue(&aux2);

if (y.exp + z.exp == j)

t->coef+=y.coef*z.coef;

}

}

enqueue(&produs,t);

}

k = size(produs);

for (i=0;i<=k-1;i++){

z = *(p_nod*)dequeue(&produs);

printf("%.2lf %d\n",z.coef,z.exp);

}

return 0;

}

Sortare radix folosind cozi

Se foloseste urmatoarea interfata pentru tipul de date Coada:

queue.h

#ifndef _QUEUE_H

#define _QUEUE_H

typedef struct nod{

void* data;

struct nod* next;

}q_nod;

typedef q_nod* Queue;

/* adaugare in coada */

int enqueue(Queue*, void*);

/* extragere din coada */

void* dequeue(Queue*);

/* inspectarea primului element */

void* Front(Queue);

/* test coada vida */

int isEmpty(Queue);

/* dimensiunea cozii */

int size(Queue);

#endif

queue.c

#include "stdlib.h"

#include "queue.h"

int enqueue (Queue *Q,void *x){

Queue aux,pus;

aux = *Q;

if (aux!=NULL){

while (aux->next!=NULL)

aux = aux->next;

pus = (Queue)malloc(sizeof(q_nod));

pus->data = x;

aux->next = pus;

pus->next = NULL;

return 0; }

else {

aux = (Queue)malloc(sizeof(q_nod));

aux->data = x;

aux->next = NULL;

*Q = aux;

return 0;

}

}

void* dequeue (Queue *Q){

Queue aux;

aux = *Q;

if(*Q==NULL) return NULL;

void* x = (*Q)->data;

*Q = (*Q)->next;

free(aux);

return x;

}

void* Front (Queue Q){

if (Q==NULL)

return NULL;

else

return Q->data;

}

int isEmpty (Queue Q){

return Q==NULL;

}

int size (Queue Q){

int k = 0;

Queue aux = (Queue)malloc(sizeof(q_nod));

aux = Q;

while (aux!=NULL){

k++;

aux = aux->next;

}

return k;

}

Sortarea este urmatoarea:

#include "queue.h"

#include "stdio.h"

#include "stdlib.h"

#include "math.h"

int rangmax (int n, int *X){

int xm = X[0];

int k, r;

for (k=0; k

if(X[k] > xm)

xm = X[k];

r = 0;

while (xm > 0){

r++;

xm/=10;

}

return r;

}

void Distribuie (int n, int* X, Queue* QC, int r){

int nc=0, ind, i, j, *pi;

for(i=0 ; i<=n-1 ; i++){

int t=X[i];

for(j=0; j <=r-1; j++)

t /= 10;

ind = t % 10;

if(isEmpty(QC[ind]))

nc++;

pi = (int*)malloc(sizeof(int));

*pi = X[i];

enqueue(&QC[ind], pi);

}

}

void Colecteaza (Queue* QC, int* X){

int j, i=0, *pi;

for (j=0; j<=9; j++)

while(!isEmpty(QC[j])){

pi = dequeue(&QC[j]);

X[i] = *pi;

i++;

free(pi);

}

}

void RadixSort (int n, int* X){

int rmx, i, r;

Queue QC[10];

for(i=0; i<=9 ; i++)

QC[i]= NULL;

rmx = rangmax(n, X);

for (r=0; r<=rmx; r++){

Distribuie(n, X, QC, r);

Colecteaza(QC, X);

}

}

int main(){

int n, i;

int *x;

scanf("%d", &n);

x = (int*)malloc(n*sizeof(int));

for(i=0; i<=n-1; i++)

scanf("%d", &x[i]);

RadixSort(n, x);

for(i=0; i<=n-1 ; i++)

printf("%5d ", x[i]);

printf("\n");

free(x);

return 0;

}