Implementarea grafurilor cu ajutorul matricei de adiacenta

Implementarea grafurilor cu ajutorul matricei de adiacenta

Tema nr. 5:

Scrieti programul C care permite crearea si vizualizara sub forma naturala a unui graf implementat cu ajutorul matricei de adiacenta varianta I. (Se va afisa si matricea de adiacenta)

Analiza:

Un graf este format dintr-o multime de noduri (varfuri) si o multime de arce (muchii). Astfel, vom nota graful ce are multimea nodurilor ( este numarul de noduri ale grafului), si multimea arcelor .

Matricea de adiacenta este o matrice patratica de ordinul , cu elemente booleene, in care elementul de pe pozitia este TRUE d.n.d. exista arc de la nodul la nodul , adica matricea definita astfel:

Deoarece limbajul C nu are definit tipul de date boolean, in implementarea acestei matrice intr-un progam C vom folosi in locul valorilor TRUE si FALSE valorile 1 si respectiv 0.

Un prim pas pe care trebuie sa-l realizam in implementarea grafurilor cu ajutorul matricei de adiacenta este stabilirea unei corespondente intre numele nodurilor si indicii de acces ai nodurilor in matricea de adiacenta. Aceasta corespondenta poate fi stabilita implicit prin alegerea corespunzatoare a tipului de baza al multimii nodurilor, sau explicit prin realizarea unei asocieri definita pe multimea nodurilor cu valori in multimea intregilor (care sunt indicii de acces ai nodurilor in cadrul matricei de adiacenta).

Pentru usurinta descrierii algoritmilor de prelucrare a grafurilor, in cele ce urmeaza vom denumi nodurile prin litere consecutive ale alfabetului latin, in acest caz putand realiza conversia directa de la tipul nodului (caracter) la tipul intreg prin functii specifice de limbaj.

Functia C care realizeaza aceasta conversie o vom denumi index, si o definim astfel:

int index(char c)

/* index */

In prelucrarea grafurilor implementate cu ajutorul matricei de adiacenta putem considera ca fiecare nod este legat cu el insusi, ceea ce se realizeaza in matricea de adiacenta prin valoarea TRUE pe diagonala principala. Acest lucru nu este insa obligatoriu, putand fi precizat de la caz la caz.

Exemplu: Sa consideram graful:

Multimea nodurilor este

Putem construi urmatorul tabel:

unde am marcat cu "x" existenta arcului de la nodul ce da numele liniei la nodul ce da numele coloanei, deci matricea de adiacenta este:

Deoarece un graf este precizat prin multimea nodurilor si multimea arcelor, in cazul prelucrarii grafului cu ajutorul unui sistem de calcul graful va fi o data de intrare, deci va trebui sa stim care sunt modalitatile de reprezentare a celor doua multimi. Cel mai simplu mod de a realiza acest lucru este de a citi direct matricea de adiacenta (de la intrare), insa acest lucru nu este eficient in cazul matricelor rare, de aceea se obisnuieste ca intr-o prima etapa sa se precizeze multimea nodurilor grafului, iar in cea de-a doua etapa sa precizam multimea nodurilor care imi definesc arcele.

In cazul reprezentarii implicite a grafului cu ajutorul matricei de adiacenta prima etapa poate sa lipseasca (nu ne intereseaza care este numele nodurilor, ci numai cate sunt), urmand doar sa precizam multimea de noduri care imi dau arcele, ordinea nefiind importanta.

Programul:

#include <conio.h>

#include <graphics.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h> // for exit

#include <ctype.h> // for toupper

#define PI 2*asin(1)

#define R 200 //raza cercului mare (imaginar)

#define r 20    //raza cercului mic (nodul)

#define CALE 'C:BORLANDCBGI'

#define nMax 10 //nr max de noduri admise

int g[nMax][nMax];

int i,j,k,n;

char n1,n2;

int x0,y0,xi,yi,xj,yj,x,y;

void initializare_mod_grafic(void);

void desenare(int n);

int index(char c);

void afisare_matrice(void);

void sterge(void);

void main(void)

initializare_mod_grafic();

desenare(n);

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

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

g[i][j]=0; //initializarea elem matricei de adiacenta

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

g[i][i]=1; //pres ca exista arc de la un nod la el insusi

printf('nIntroduceti arce? (D/N) ');

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

while(ch=='D')

printf('Al doilea nod: ');

fflush(stdin); scanf('%c',&n2);

j=index(n2);

if((j<0) || (j>=n))

g[i][j]=1;

g[j][i]=1; // pres ca graful nu e orientat

xi = x0 + R*cos(2*i*PI/n);

yi = y0 - R*sin(2*i*PI/n);

xj = x0 + R*cos(2*j*PI/n);

yj = y0 - R*sin(2*j*PI/n);

setcolor(WHITE);

line(xi,yi,xj,yj);

afisare_matrice();

alt_arc:

sterge();

gotoxy(1,2);

printf('Mai introduceti un arc? ');

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

}

sterge();

gotoxy(1,2);

printf('Asta a fost tot. Bye!n');

afisare_matrice();

getch();

closegraph();

} /* main */

void initializare_mod_grafic(void)

} /* initializare_mod_grafic */

void desenare(int n)

;

x0 = getmaxx()/2+90; //'deplasam' graful spre dreapta pt a putea reprez mat de adi

y0 = getmaxy()/2;

for(k=0; k<n; k++)

setcolor(WHITE);

} /* desenare */

int index(char c)

/* index */

void afisare_matrice(void)

} /* afisare_matrice */

void sterge(void)

Observatii:

Varianta I de implementare a unui graf cu ajutorul matricei de adiacenta este destul de "slaba" deoarece matricea de adiacenta a grafului si reprezentarea fizica a acestuia (desenul) nu sunt "legate" (daca modificam matricea de adiacenta nu o sa se modifice si reprezentarea fizica a grafului). Din acest motiv:

Nu se pot adauga noi noduri grafului pe durata rularii programului

Nu se pot sterge noduri ale grafului

Nu se pot sterge arce dupa ce au fost adaugate

Numele nodurilor vor fi litere consecutive ale alfabetului, neexistand posibilitatea denumirii arbitrare a nodurilor, sau posibilitatea ca nodurile sa contina si informatii.

Astfel, in momentul introducerii unui nou arc desenul se modifica in acelasi timp cu matricea de adiacenta, insa fara o legatura fizica intre ele, ceea ce ne duce cu gandul la tema laboratorului anterior, in care am realizat un desen care simula reprezentarea naturala a unui graf, si astfel putem spune ca acest program mimeaza un graf real.

Deci avem nevoie de o implementare mai puternica si mai flexibila a unui graf, care o vom introduce in laboratorul urmator

Din motive de design am ales ca graful sa nu mai fie pozitionat exact in centrul ecranului, ci l-am deplasat spre dreapta pentru a putea afisa matricea de adiacenta in coltul din stanga jos al ecranului, astfel putem urmari in momentul in care introducem un nou arc cum se modifica desenul si matricea de adiacenta. Tot din motive de design am pastrat modul de interogare cu privire la introducerea de noi arce din seminarul anterior, fara nici o modificare.