Scrieti programul C care realizeaza calculul inchiderii tranzitive folosind algoritmul lui Warshall
Descrierea algoritmului
Warshall a fost cel care a determinat un algoritm mai eficient pentru calculul inchiderii tranzitive decat cel anterior. In acest sens declaram o matrice Drumk astfel incat Drumk[i,j] == 1 daca exista un drum de la no 232h71c dul i la nodul j care nu trece prin nici un alt nod cu numarul > k, exceptamd eventual nodurile i si j. Subintelegem ca am denumit nodurile 1, 2, , n. k poate lua valori de la 0 la nr.noduri.
Drum0[i,j] este matricea care are pe pozitia ij true (daca exista un drum de la i la j care nu trece prin nici un nod > 0, cu exceptia lui i si j. Deci Drum0[i,j]==Arce[i,j], deoarece singura posibilitate de a ajunge de la i la j este calea directa de la i la j, adica arcul(i,j).
Ne propunem sa determinam Drumk+1[i,j] pornind de la Drumk. Evident Drumk[i,j]==1 acolo unde Drumk[i,j]=1, deoarece, daca avem un drum de la i la j care nu trece prin nici un nod cu numarul > k, vom avea drum de la i la j care nu trece prin nici un nod cu numarul > k+1.
Singura posibilitate ca Drumk+1[i,j]==1 si Drumk[i,j]= 0 este daca exista un drum de la i la prin nodul k+1, care insa sa treaca numai prin nodurile de la 1 la k. Deci vom avea un drum de la nodul i la nodul k+1 care nu trece prin nici un nod cu indice > k.
Cu alte cuvinte, Drumk+1[i,j] == 1 daca:
Drumk[i,j] == 1 sau
Drumk[i,k+1] == 1 si Drumk[k+1,j] == 1 .
=>Drumk+1[i,j] == Drumk[i,j] || (Drumk[i,k+1] && Drumk[k+1,j] ) .
Conform acestui algoritm Drum0 == Arce si Drumnrnoduri == Drum deci chiar matricea inchiderii tranzitive cautata .
Observatii:
Algoritmul lui Warshall,care determina matricea Drumnrnoduri determina chiar matricea Drum, doar ca algoritmul este de ordinul n3 , unde n coincide cu numarul de noduri ale grafului .
Programul C:
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <math.h>
#include <process.h>
#include <ctype.h>
#define PI (2*asin(1))
#define r 100
#define CALE 'C:BORLANDCBGI'
#define NrNoduri 4
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipMatAdi Adi, Drum;
void Atribuire(TipMatAdi a, TipMatAdi b)
/* Atribuire */
void Produs(TipMatAdi a, TipMatAdi b, TipMatAdi c)
}/* Produs */
void Warshall(TipMatAdi Adi, TipMatAdi Drum)
/* Warshall */
void InitGraf(Graf *g)
/* InitGraf */
void creare()
if(ok)
i--;
else
g.Noduri[i] = x;
}
printf('Trasati un arc?(d/n)');fflush(stdin);
scanf('%c',&c);c=toupper(c);
while(c=='D')
printf('Trasati un arc?(d/n)'); fflush(stdin);
scanf('%c', &c); c = toupper(c);
}
}/* creare */
void initializare_mod_grafic(void)
} /* initializare */
void afisareNoduri(Graf g)
int i, xi, yi, x0, y0;
x0 = getmaxx()/2;
y0 = getmaxy()/2;
for(i=0; i<NrNoduri; i++)
setcolor(WHITE);
}/* afisareNoduri */
void afisareGraf(Graf g)
outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');
getch();
closegraph();
}/* afisareGraf */
int CautNod(Graf g,TipCheie cheie)
/* CautNod */
void main(void)
printf('Apasati o tasta pentru a continua!n');
getche();
break;
case 'E':break;
default:printf('Optiune gresita!n');
}
}while(c != 'E');
}/* main */
|
