Se da un graf G precizat prin multimea nodurilor si multimea arcelor sale, folosind ca implementare implementarea prin matrice de adiacenta varianta a II-a

Se da un graf G precizat prin multimea nodurilor si multimea arcelor sale, folosind ca implementare implementarea prin matrice de adiacenta varianta a II-a. Sa se determine intre care doua noduri ale grafului exista drum. Se va afisa atat matricea de adiacenta, c 717f58h at si matricea drumurilor! (Warshall).

Descrierea algoritmului

Warshall a fost cel care a determinat un algoritm mai eficient pentur calculul inchiderii tranzitive decat cel anterior. In acest sens ne declaram o matrice Drum_k astfel incat Drum_k[i,j] == 1 daca exista un drum de la nodul i la nodul j care nu trece prin nici un alt nod cu numarul > k, exceptamd eventual nodurile is si j. Subintelegem ca am denumit nodurile 1, 2, , n. k poate lua valori de la 0 la nrnoduri.

Drum₀[i,j] este matricea care are e 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 Drum₀[i,j]==Arce[i,j], deoarece singura posibilitate de a ajunge de al i la j este calea directa de la i la j, adica arcul(i,j).

Ne propunem sa determinam Drum_k+1[i,j] pornind de la Drum_k. Evident Drum_k[i,j]==1 acolo unde Drum_k[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 Drum_k+1[i,j]==1 di Drum_k[i,j]==0 este daca exista un drum de la i la jprin nodul k+1, care insa sa treaca numai prin nodurile de al 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, Drum_k+1[i,j] == 1 daca:

Drum_k[i,j] == 1 sau

Drum_k[i,k+1] == 1 si Drum_k[k+1,j] == 1 .

=>Drum_k+1[i,j] == Drum_k[i,j] || (Drum_k[i,k+1] && Drum_k[k+1,j] ) .

Conform acestui algoritm Drum₀ == Arce si Drum_nrnoduri == Drum deci chiar matricea inchiderii tranzitive cautata .

Observatii:

Algoritmul lui Warshall , care determina matricea Drum_nrnoduri determina chiar matricea Drum , doar ca algoritmul este de ordinul n³ , unde n coincide cu numarul de noduri ale grafului .

Rezolvare:

Se da un graf G precizat prin multimea nodurilor si multimea arcelor sale, folosind ca implementare implementarea prin matrice de adiacenta varianta a II-a. Sa se determine intre care doua noduri ale grafului exista drum. Se va afisa atat matricea de adiacenta, c 717f58h at si matricea drumurilor! (Warshall).

#include<stdio.h>

#include<graphics.h>

#include<alloc.h>

#include<conio.h>

#include<dos.h>

#include<ctype.h>

#include<stdlib.h>

#include<math.h>

#define R 200

#define r 15

#define maxN 20

#define PI M_PI

typedef char TipCheie;

typedef TipCheie TipEl;

typedef int TipContor;

typedef TipEl TipTabEl[maxN];

typedef int TipMatAdi[maxN][maxN];

typedef struct

graf;

typedef struct

TipArc;

graf g;

TipEl e,c1,c2;

TipMatAdi Drum;

int c,x0,y0,xi,yi,xj,yj;

double x1,y1,x2,y2,x3,y3,alfa,alfa1,alfa2;

int IndiceNod;

TipArc IndiceArc;

int i,j;

char s[2]=;

void init_mod_grafic(void)

}/*init mod_grafic*/

int Cauta(graf g, TipCheie cheia)

void InserArc(graf *g, TipArc IndiceArc)

/*InserArc*/

void InserNod(graf *g, TipEl e)

g->Arce[g->Contor-1][g->Contor-1]=1;

void DesenareNoduri(int n)

setcolor(WHITE);

}/*DesenareNoduri*/

void TraseazaArc(int i, int j)

void InserareArc(void)

else printf('al doilea nod eronat!g.Contor');

}

else printf('primul nod eronat!g.Contor');

} /*InserareArc*/

void CreareGraf(void)

/*precizare multimilor arcelor*/

if(g.Contor>0)

/*while*/

}

} /*CreareGraf*/

void SuprimareArc(void)

else printf('al doilea nod eronat!g.Contor');

}

else printf('primul nod eronat!g.Contor');

}/*SuprimareArc*/

void DesenareGraf(void)

setcolor(WHITE);

} /*DesenareGraf*/

void Atribuire(TipMatAdi a,TipMatAdi b)

//atribuire

void AfisMat(TipMatAdi a)

}//afisare matrice

void Warshall(TipMatAdi Adi,TipMatAdi Drum)

void main()

clrscr();

closegraph();

init_mod_grafic();

x0=getmaxx()/2+80;

y0=getmaxy()/2;

printf('C - Crearen');

printf('A - InserareArcn');

printf('S - SuprimareArcn');

printf('N - InserareNodn');

printf('D - SuprimareNodn');

printf('T - Afisare matrice drumn');

printf('E - iesiren');

printf('Introduceti op: ');

fflush(stdin); scanf('%c',&op); op=toupper(op);

cleardevice();

}

closegraph();